A Digestion of A Counterexample to the Generalized Lax Conjecture
Preliminaries on Hyperbolic Polynomials
The generalized Lax conjecture was a central topic of study in the field of hyperbolic polynomials. Hyperbolic polynomials in general serve as a bridge between the seemingly disparate fields of algebraic geometry and convex optimization, as each hyperbolic polynomial gives rise in a natural way to a convex cone. The generalized Lax conjecture in particular gave a characterization of the possible convex cones that could arise in this way. The conjecture was disproven in October of 2026 by an internal model from OpenAI, which provided an explicit counterexample to the stated characterization. In a sense, the conjecture being false is the more interesting possibility, as it suggests that there is more richness to the theory of hyperbolic polynomials than previously thought. This post is an attempt to understand this counterexample and its generalizations.
A homogeneous polynomial $p \in \R[x_1, \dots, x_n]$ is said to be hyperbolic with respect to $v \in \R^n$ if $p(v) \neq 0$ and for each $x \in \R^n$, the univariate polynomial $p(x-tv)$ has only real roots. The hyperbolicity cone associated to such a polynomial is then
$$ \Lambda_p = \{x \in \R^n : p(x-tv) \text{ has only nonnegative roots}\}. $$The prototypical example of a hyperbolic polynomial is the determinant of an $n\times n$ symmetric matrix, which is hyperbolic with respect to the identity matrix due to the spectral theorem, and whose hyperbolicity cone is the set of positive semidefinite matrices. The generalized Lax conjecture essentially states that every hyperbolicity cone can be expressed as the intersection between a positive semidefinite cone and a linear subspace [1]. Such a cone is said to be spectrahedral [3].
There are two steps to disproving the generalized Lax conjecture: firstly, one must find a polynomial $p$ and show that it is hyperbolic, and secondly one must show that $\Lambda_p$ is not spectrahedral. Both of these steps are nontrivial. While showing that a polynomial is hyperbolic is not always easy, there have been many interesting constructions of hyperbolic polynomials in the literature [2]. None of these constructions had been shown to have nonspectrahedral hyperbolicity cones in the past (though in light of the disproof of the generalized Lax conjecture, one may wish to revisit some of these earlier constructions to see if they also are counterexamples to the conjecture). So one suspects that showing that the hyperbolicity cone is not spectrahedral will be the hard part. The proof given by OpenAI actually reduces the issue of showing that the cone to the well known fact that there exist positive operators which are not completely positive, a distinction that has been studied in the context of quantum mechanics for many years [4].
A positive operator is a linear map $\Phi :\S^n \rightarrow \S^m$ that sends positive semidefinite matrices to positive semidefinite matrices, and a completely positive such operator is one that takes the form of a `Kraus operator’, which is to say it is of the form
$$ \Phi(X) = A^{\intercal}(I\otimes X)A, $$where $A : \R^m \rightarrow \R^n \times \R^k$ for some $k$.
It is noteworthy that there is an equivalence between such linear operators and biquadratic forms, meaning polynomials that are separately homogeneous of degree 2 in two separate blocks of variables, so that a positive operator corresponds precisely a nonnegative biquadratic form, and a completely positive one corresponds to a sum-of-squares biquadratic form. In this way, the distinction between positive operators and completely positive operators is related to the distinction between sums-of-squares polynomials and nonnegative polynomials.
The most general construction of a hyperbolicity cone that can be derived from the OpenAI paper shows that for any nonnegative triquadratic form, which can be associated to a quadratic family of positive maps, there is an associated hyperbolicity cone. The OpenAI paper further shows that if this triquadratic form is constructed from a extremal nonnegative biquadratic form that is not sums-of-squares, then the resulting hyperbolicity cone is not spectrahedral.
Another paper in the same OpenAI release shows that there is a hyperbolic polynomial whose hyperbolicity cone is not even a spectrahedral shadow. We will not discuss this example here, except to note that the relevant hyperbolicity cone that serves as a counterexample to that construction also arises from the same construction applied to a certain nonnegative triquadratic form. Also, the OpenAI paper that produced the counter example to the generalized Lax conjecture applied some additional ideas not mentioned here that reduce the number of variables and the size of the counter example.
This document is constructed so that the proofs of each major result immediately follows the statement, but it is hidden underneath a dropdown menu. This is meant to give the reader the ability to go over the argument at a high level, and then pass through the details afterwards.
The Construction: Generalized Schur Complements and Positive Operators
The hyperbolicity cones that are ultimately shown to be nonspectrahedral arise from a natural and fairly general construction. To motivate the construction, we will recall the Schur complement characterization of the positive semidefinite cone:
$$ \S^n_+ = \overline{\{\begin{pmatrix}X & Y \\ Y^{\T} & Z\end{pmatrix} : X \succ 0,\ Z \succ Y^{\T}X^{-1}Y\}}. $$We will note a few features of the map $(X,Y) \mapsto Y^{\T}X^{-1}Y$:
- It is linear in $X^{-1}$.
- It is quadratic in $Y$.
- For any $Y$ and any $X \succeq 0$, $Y^{\T}X^{-1}Y \succeq 0$.
We will say that a linear map $\Phi : \S^n \rightarrow \S^m$ is positive if for every $X \succeq 0$, $\Phi(X) \succeq 0$. We will then define a quadratic family of positive maps (QFPM) to be a polynomial function $\Phi : \S^n \times \R^k \rightarrow \S^m$ so that $\Phi(X,Y)$ is linear in $X$, quadratic in $Y$, and for every $Y$, the linear map $\Phi(\cdot, Y)$ is positive.
We then come to the construction of the relevant hyperbolicity cone.
Theorem 1
Let $\Phi(X,Y)$ be a QFPM. Then the following is a hyperbolicity cone,
$$ H_{\Phi} = \overline{\{(X,Y,Z) \in \S^m \times \S^n \times \R^k : X \succ 0,\ Z \succ \Phi(X^{-1},Y)\}}, $$for the polynomial
$$ p_{\Phi}(X,Y,Z) = \det\big(\det(X)Z - \Phi(\adj(X), Y)\big), $$which is hyperbolic with respect to $(I,0,I)$. Here $\adj(X) = \det(X) X^{-1}$ for invertible $X$ is the adjugate of $X$.
Click to expand the proof
We will use repeatedly in this proof that if $X$ is nonsingular, then
$$ p_{\Phi}(X,Y,Z) = \det(X)^m\det\big(Z - \Phi(X^{-1}, Y)\big). $$The proof breaks into two parts: firstly that $p_{\Phi}$ is indeed hyperbolic, and secondly that its hyperbolicity cone is $H_{\Phi}$. We will show this in two lemmas:
Lemma
For any QFPM $\Phi$, the polynomial
$$ p_{\Phi}(X,Y,Z) = \det\big(\det(X)Z - \Phi(\adj(X), Y)\big), $$is hyperbolic with respect to $(I,0,I)$.
Click to expand the proof
We consider $p_{\Phi}(X+tI,Y,Z+tI)$ where $\im t > 0$ and $(X,Y,Z) \in \S^n \times \R^k \times \S^m$, and we want to show that this is nonzero. Assume for contradiction that $p_{\Phi}(X+tI,Y,Z+tI) = 0$ with $\im t > 0$.
Note that if $\det(X+tI) = 0$, then $t$ would be real because it would be the negative of an eigenvalue of a symmetric matrix. Thus, we may assume that $\det(X+tI) \neq 0$, and therefore that
$$ p_{\Phi}(X+tI,Y,Z+tI) = \det(X+tI)^{m} \det\big(Z+tI - \Phi((X+tI)^{-1}, Y)\big) = 0. $$We conclude that $Z + tI - \Phi((X+tI)^{-1}, Y)$ is singular. Let $w \in \C^m$ be in the kernel of this matrix, and let us consider
$$ \begin{aligned} 2\im \big(w^\dagger (Z + tI - \Phi((X+tI)^{-1}, Y)) w \big) &= \frac{1}{i} \big(w^\dagger (Z + tI - \Phi((X+tI)^{-1}, Y)) w - w^\T \overline{(Z + tI - \Phi((X+tI)^{-1}, Y))}\, \overline{w} \big) \\ &= \frac{1}{i} \big(w^\dagger (Z + tI - \Phi((X+tI)^{-1}, Y)) w - w^\dagger (Z + tI - \Phi((X+tI)^{-1}, Y))^{\dagger} w \big) \\ &= w^\dagger\, \iota\big(Z + tI - \Phi((X+tI)^{-1}, Y)\big)\, w, \end{aligned} $$where
$$ \iota(X) = \frac{1}{i}(X - X^{\dagger}). $$We see that
$$ \iota\big(Z + tI - \Phi((X+tI)^{-1}, Y)\big) = \im t\, I - \Phi(\iota((X+tI)^{-1}), Y), $$where we use the fact that $\Phi(X,Y)$ is linear in $X$ with real coefficients, and that $X$ is symmetric.
Our final claim before concluding that $p_{\Phi}$ is hyperbolic is that $\iota((X+tI)^{-1})$ is negative definite. This finishes the argument because the fact that $\Phi(\cdot, Y)$ is positive would also imply that
$$ 0 \preceq \im t\, I \preceq \im t\, I - \Phi(\iota((X+tI)^{-1}), Y), $$and therefore that $\im\, w^\dagger \iota(Z + tI - \Phi((X+tI)^{-1}, Y)) w < 0$, contradicting the fact that $w$ is in the kernel of this matrix.
The fact that $\iota((X+tI)^{-1})$ is negative definite can be checked eigenvalue by eigenvalue of this matrix; every eigenvalue of $(X+tI)^{-1}$ is of the form $\frac{1}{\lambda + t}$ where $\lambda$ is an eigenvalue of $X$, and thus the eigenvalues of $\iota((X+tI)^{-1})$ are of the form
$$ \im \frac{1}{(\lambda + \re t) + i\,\im t} = \im \frac{\overline{t}}{|t|^2} = - \frac{\im t}{|t|^2} < 0. $$$\Box$
Lemma
For any QFPM $\Phi$, the hyperbolicity cone of the polynomial
$$ p_{\Phi}(X,Y,Z) = \det\big(\det(X)Z - \Phi(\adj(X), Y)\big), $$with respect to $(I,0,I)$ is
$$ H_{\Phi} = \overline{\{(X,Y,Z) \in \S^m \times \S^n \times \R^k : X \succ 0,\ Z \succ \Phi(X^{-1},Y)\}}, $$
Click to expand the proof
We will use the characterization that the interior of the hyperbolicity cone of $p_{\Phi}$ is the connected component of the complement of the zero set of $p_{\Phi}$ containing $(I,0,I)$.
Note that because
$$ \{(X,Y,Z) \in \S^m \times \S^n \times \R^k : X \succ 0,\ Z \succ \Phi(X^{-1},Y)\} $$is open, it is the interior of $H_{\Phi}$. Thus, it is clear that $(I,0,I) \in H_{\Phi}^o$. It remains to show that that $H_{\Phi}^o$ is connected, $p_{\Phi}$ does not vanish on $H_{\Phi}^o$ and that $p_{\Phi}$ does vanish everywhere on the boundary of $H_{\Phi}$.
To see that $H_{\Phi}^o$ is connected and indeed path connected, note that for any $(X,Y,Z) \in H_{\Phi}^o$ and $1 \ge s \ge 0$, $(X,sY,Z) \in H_{\Phi}^o$. Then we note that $(t X + (1-t)I, 0, t Z + (1-t)I) \in H_{\Phi}^o$ for any $1 \ge t \ge 0$, and so we are done.
It is also clear that $p_{\Phi}$ does not vanish on $H_{\Phi}^o$. If $(X,Y,Z) \in H_{\Phi}^o$, then
$$ p_{\Phi}(X,Y,Z) = \det(X)^{m} \det(Z - \Phi(X^{-1}, Y)) > 0. $$It remains to show that $p_{\Phi}(X,Y,Z) = 0$ for any $(X,Y,Z) \in \partial H_{\Phi}$. For this, we note that if $(X,Y,Z) \in \partial H_{\Phi}$, then either $X$ is singular or $Z - \Phi(X^{-1}, Y)$ is singular. If $X$ is nonsingular, and $Z - \Phi(X^{-1}, Y)$ is singular, then it is clear from our above factorization that $p_{\Phi}(X,Y,Z) = 0$. If $X$ is singular, then
$$ p_{\Phi}(X,Y,Z) = \det\big(\det(X)Z - \Phi(\adj(X), Y)\big) = \det\big(\Phi(\adj(X),Y)\big). $$If $X$ is of rank less than $n-1$, then $\adj(X) = 0$, and we can see that $p_{\Phi}(X,Y,Z) = 0$. So we must finally consider the case that $X$ is singular, of rank $n-1$, and $X \in H_{\Phi}$. Under these assumptions, we must show that $\Phi(\adj(X),Y)$ is singular, so that $p_{\Phi}(X,Y,Z) = 0$.
Suppose that $\Phi(\adj(X),Y)$ is not singular, and consider a sequence $\{(X_i, Y_i, Z_i)\}_{i=0}^{\infty}$ where each $(X_i, Y_i, Z_i) \in H_{\Phi}^o$ and $\lim_{i\rightarrow \infty}(X_i, Y_i, Z_i) = (X,Y,Z)$. We can consider the spectral decomposition of each $X_i$,
$$X_i = \sum_{k=1}^n \lambda_{ik} v_{ik}v_{ik}^{\T},$$where $0<\lambda_{i1}\le \lambda_{i2} \le \lambda_{i3}\dots\le \lambda_{in}$ are the eigenvalues of $X_i$ and each $v_{ik}$ is a unit eigenvector associated to the eigenvalue $\lambda_{ik}$. Because the eigenvalues of a symmetric matrix are continuous functions of that matrix,
$$\lim_{i\to\infty} \lambda_{ik}=\lambda_k(X)$$for each $k$. In particular, because $X$ is of rank $n-1$, for all $i$ large enough, and all $k > 1$, $\lambda_{ik} > \epsilon$ and $\lambda_{i1} < \epsilon$ for some $\epsilon > 0$. We therefore conclude that the projection onto the eigenspace of the minimum eigenvalue of each $X_i$, $v_{i1}v_{i1}^{\T}$, is unique and therefore continuous as a function of $X$, and so we have that $\lim_{i\rightarrow \infty} v_{i1}v_{i1}^{\T} = vv^{\T}$, where $v$ is the unit vector in the kernel of $X$. This implies that
$$ \Phi(X_i^{-1}, Y) = \Phi\Big(X_i^{-1}-\tfrac{1}{\lambda_{i1}}v_{i1}v_{i1}^{\T},Y\Big) + \Phi\Big(\tfrac{1}{\lambda_{i1}}v_{i1}v_{i1}^{\T},Y\Big) \succeq \tfrac{1}{\lambda_{i1}}\Phi(v_{i1}v_{i1}^{\T},Y). $$We have by continuity of $\Phi$ that $\lim_{i\rightarrow \infty}\Phi(v_{i1}v_{i1}^{\T},Y)= \Phi(vv^{\T},Y) \neq 0$, and so, for $i$ large enough, $\|\Phi(v_{i1}v_{i1}^{\T},Y)\|_{\op} > \delta$ for some $\delta > 0$. This implies that for $i$ large enough,
$$\|Z_i\|_{\op} \ge \|\Phi(v_{i1}v_{i1}^{\T},Y)\|_{\op} \ge \frac{\delta}{\lambda_{i1}}.$$Since
$$\lim_{i\to\infty} \lambda_{i1} = 0,$$we see that $\|Z_i\|_{\op}$ is unbounded, and so the limit of the $Z_i$ does not exist. This contradiction implies that $\Phi(\adj(X),Y)$ is singular, and we are done.
$\Box$
Combining these two lemmas gives the theorem.
$\Box$
Remark
This definition is remarkably close to that of a Siegel cone for the PSD cone, which amounts to the special case of this construction when $n = 1$. Siegel cones are of interest because every homogeneous cone can be constructed by applying the Siegel cone operation repeatedly a one dimensional cone [5].
Spectrahedral Cones and Completely Positive Maps
There are in fact many hyperbolicity cones that result from this construction. We now want to find one such cone which is not spectrahedral. Or, to put it another way, we want to find necessary conditions that $\Phi$ needs to satisfy in order for this cone to be spectrahedral, and then show that some $\Phi$ yields a hyperbolicity cone that does not satisfy those conditions.
One sufficient condition for the cone to be spectrahedral is for $\Phi$ to be completely positive in the following sense: there exist some positive operator $E : \S^n \rightarrow \S^{n'}$ and linear map $A : \R^k \rightarrow \R^{n' \times m}$ so that
$$ \Phi(X,Y) = A(Y)^{\T} E(X) A(Y), $$in which case
$$ H_{\Phi} = \{(X,Y,Z) : \begin{pmatrix} E(X) & A(Y)^{\T} \\ A(Y) & Z\end{pmatrix} \succeq 0\}. $$The first thing that the OpenAI paper [8] did to show that there is a nonspectrahedral hyperbolicity cone is to show a partial converse to this result.
Recall that a positive operator is unital if $\Phi(I) = I$.
Theorem 2
Let $\Phi(X,Y)$ be a QFPM, and suppose that $H_{\Phi}$ is spectrahedral. Then there exist unital positive operators $E : \S^n \rightarrow \S^{n'}$ and $G: \S^m \rightarrow \S^{m'}$, together with a linear map $F : \R^k \rightarrow \R^{n' \times m'}$ so that
$$ H_{\Phi} = \left\{(X,Y,Z) \in \S^n \times \R^k \times \S^m : \begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z) \end{pmatrix} \succeq 0\right\}. $$
Click to expand the proof
Since $H_{\Phi}$ is spectrahedral, there exists some natural number $d$ and a linear map $L : \S^n \times \R^k \times \S^m \rightarrow \S^d$ so that $(X,Y,Z) \in H_{\Phi} \Leftrightarrow L(X,Y,Z) \succeq 0$. We may assume by applying a compression transformation if necessary that there is no common kernel for the image of $L$, and by applying a congruence transformation, we may assume that $L(I,0,I)$ is positive definite.
We may write $L(X,Y,Z) = L_1(X) + L_2(Y) + L_3(Z)$, where $L_1 : \S^n \rightarrow \S^d$, $L_2 : \R^k \rightarrow \S^d$, and $L_3 : \S^m \rightarrow \S^d$.
Now, we may perform a block decomposition on $\S^d$: let $U = \bigcap_{X \in \S^n} \ker(L_1(X))$ (which may in principle be $0$), and we can perform a congruence transformation sending $U$ to the span of the last $\dim(U)$ coordinate vectors, so that in block matrix form,
$$ L_1(X) = \begin{pmatrix} E(X) & 0 \\ 0 & 0\end{pmatrix}, $$for some positive map $E : \S^n \rightarrow \S^{d'}$. We can similarly block decompose $L_2$ and $L_3$ to obtain
$$ L_2(Y) = \begin{pmatrix} L_2^{11}(Y) & F(Y) \\ F(Y)^{\T} & L_2^{22}(Y)\end{pmatrix}, $$and
$$ L_3(Z) = \begin{pmatrix} L_3^{11}(Z) & L_3^{12}(Z) \\ L_3^{12}(Z)^{\T} & G(Z)\end{pmatrix}. $$We now claim that
$$(X,Y,Z) \in H_{\Phi} \iff \begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z) \end{pmatrix} \succeq 0.$$One of the key observations about this generalized Schur complement construction is that there is a natural action of $(\R^{\times})^2$ on $H_{\Phi}$, i.e.
Lemma
For $t,s \neq 0$, $(X,Y,Z) \in H_{\Phi}$ if and only if $(t^2X,stY, s^2 Z) \in H_{\Phi}$.
Click to expand the proof
We will show this for $(X,Y,Z) \in H_{\Phi}^o$ and then claim that it therefore holds for $H_{\Phi}$ by continuity.
Note that
\[ s^2Z \succ \Phi((t^2X)^{-1}, st Y) \Leftrightarrow s^2Z \succ \frac{(s t)^2}{t^2}\Phi(X^{-1}, Y) \Leftrightarrow Z \succ \Phi(X^{-1}, Y). \]$\Box$
Using this observation, we can show the following:
Lemma
Both $L_2^{22}(Y)$ and $L_2^{11}(Y)$ are identically $0$.
Click to expand the proof
Fix some $Y \in \R^k$, and let $Z_0 = \Phi(I,Y)$. Note that for any $s$, $(I, sY, s^2Z_0), (I,-sY,s^2Z_0) \in H_{\Phi}$, and therefore we have that for any $s > 0$,
$$ s^2 L_3^{22}(Z_0) + s L_2^{22}(Y) \succeq 0, \qquad s^2 L_3^{22}(Z_0) - s L_2^{22}(Y) \succeq 0. $$Dividing by $s$ and taking the limit as $s$ approaches $0$ shows that $L_2^{22}(Y) = 0$ for any $Y \in \R^k$. A similar argument noting that $(s^2 I, s Y, Z_0), (s^2 I, -s Y, Z_0) \in H_{\Phi}$ for $s > 0$ shows that $L_2^{11}(Y) = 0$ for all $Y$.
$\Box$
From this, we can also conclude that $E(I)$ and $G(I)$ are positive definite; if they were not, $L(I,0,I)$ would have a nontrivial kernel.
We now show one direction of the equivalence.
Lemma
If $(X,Y,Z) \in H_{\Phi}$, then $\begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z) \end{pmatrix} \succeq 0.$
Click to expand the proof
Let $D_s = \begin{pmatrix} I & 0 \\ 0 & \frac{1}{s}I \end{pmatrix}$. For any $(X,Y,Z) \in H_{\Phi}$ and $s$, we have that $(X,sY,s^2Z) \in H_{\Phi}$, so
$$ D_s\big(L_1(X) + s L_2(Y) + s^2 L_3(Z)\big)D_s = \begin{pmatrix} E(X) + s^2 L_3^{11}(Z) & F(Y) + s L_3^{12}(Z) \\ F(Y)^{\T} + s L_3^{12}(Z)^{\T} & G(Z)\end{pmatrix} \succeq 0. $$Taking the limit as $s \rightarrow 0$ shows that $\begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z) \end{pmatrix} \succeq 0$.
$\Box$
Lemma
If $(X,Y,Z) \not \in H_{\Phi}$, then $\begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z) \end{pmatrix} \not \succeq 0.$
Click to expand the proof
Since $(X,Y,Z) \not\in H_{\Phi}$, $L(X,Y,Z) \not\succeq 0$. We will assume for the sake of contradiction that $\begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z) \end{pmatrix} \succeq 0.$ Because $(X,Y,Z) \not\in H_{\Phi}$, we have $(X + \delta I, Y, Z +\delta I) \not\in H_{\Phi}$ for $\delta$ small enough, yet we would in fact have that
$$\begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z) \end{pmatrix} + \delta \begin{pmatrix} E(I) & 0 \\ 0 & G(I) \end{pmatrix} \succ 0.$$So, by replacing $(X,Y,Z)$ by $(X+\delta I, Y, Z +\delta I)$ if necessary, we may assume that $\begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z) \end{pmatrix}$ is positive definite, yet $(X,Y,Z) \not\in H_{\Phi}$.
Now, we simply note that for every $s \neq 0$, $(X, sY, s^2 Z) \not\in H_{\Phi}$, and therefore,
$$ D_s\big(L_1(X) + s L_2(Y) + s^2 L_3(Z)\big)D_s = \begin{pmatrix} E(X) + s^2 L_3^{11}(Z) & F(Y) + s L_3^{12}(Z) \\ F(Y)^{\T} + s L_3^{12}(Z)^{\T} & G(Z)\end{pmatrix} \not\succeq 0, $$and in particular, the limit as $s\rightarrow 0$ of this matrix cannot be positive definite, a contradiction.
Finally, we can achieve the fact that $E$ and $G$ are unital by applying a congruence transformation and using the fact that $E(I)$ and $G(I)$ are positive definite.
$\Box$
We conclude that
$$ H_{\Phi} = \{(X,Y,Z) \in \S^n \times \R^k \times \S^m : \begin{pmatrix} E(X) & F(Y) \\ F(Y)^{\T} & G(Z)\end{pmatrix} \succeq 0\}. $$$\Box$
Thus, if $H_{\Phi}$ is spectrahedral, then it must look like the construction applied to a completely positive $\Phi$. In particular, this suggests that if a $\Phi$ which is not completely positive is passed through this construction, then $H_{\Phi}$ will not be spectrahedral. While we will not show that this is the case, we will show that if $\Phi$ is a positive map that is not completely positive and also `extremal’ in a certain sense, then $H_{\Phi}$ is not spectrahedral.
It may not seem obvious that there exists such a positive QFPM that is not completely positive. However, there is a fairly general class of constructions that will supply us with these QFPMs. For this, it is helpful to pass to an equivalent characterization of QFPMs: nonnegative triquadratic forms.
QFPMs and Nonnegative Triquadratic Forms
Preliminaries on Positive Operators and Nonnegative Biquadratic Forms
Associated to a linear map $\Phi : \S^n \rightarrow \S^m$ is the following biquadratic form $B : \R^m \times \R^n \rightarrow \R$:
$$ B(u,v) = u^{\T}\Phi(vv^{\T})u. $$By biquadratic, we mean that $B(\lambda u, \mu v) = \lambda^2 \mu^2 B(u,v)$ for any $\lambda, \mu \in \R$ and $u,v \in \R^n \times \R^m$. In fact, by dimension counting, we can see that for any biquadratic form $B$, there is some $\Phi$ so that $B(u,v) = u^{\T}\Phi(vv^{\T})u$. Thus, a biquadratic form is equivalent to a linear map $\Phi : \S^n \rightarrow \S^m$.
One reason to study $B(u,v)$ is that it is pointwise nonnegative if and only if $\Phi$ is a positive operator. This follows directly from the fact that the extreme rays of $\S^m$ are spanned by rank $1$ matrices.
One sufficient condition for $B(u,v)$ to be nonnegative is that it is a sum-of-squares of lower degree polynomials (which will necessarily be bilinear forms). A linear map associated to a sums-of-squares biquadratic form is said to be completely positive. Note that $\Phi$ being completely positive is equivalent to the statement that the map $\Phi$ is of the form $A^{\T}(I\otimes X)A$ for some $A$.
An equivalent characterization is that a linear map $\Phi$ is completely positive if and only if for every $k$, the linear map $I_k \otimes \Phi$ is positive. Such maps have been studied intently in quantum mechanics because they correspond to quantum communication channels that are respect entanglement relations, while more general positive maps do not. In particular, it is known that there are positive maps that are not completely positive, or in otherwise nonnegative biquadratic forms that are not sums-of-squares whenever $n,m > 2$.
An important example is the Choi–Lam form [6], defined as
$$ B(u,v) = \sum_{i=1}^3 u_i^2v_i^2 + \sum_{i=1}^3 u_i^2 v_{i+1}^2 - \sum_{i = 1}^3 \sum_{j=1}^3 u_iu_{i+1}v_i v_{i+1}. $$This is an example of a nonnegative biquadratic form that is not a sum of squares. It is worth noting that this particular nonnegative biquadratic form is extreme, meaning that it cannot be written in a nontrivial way as a sum of other nonnegative biquadratic forms [7]. This is the key fact that the ultimate nonspectrahedrality argument relies on. However, it is also worth noting that any extremal nonnegative biquadratic form will suffice for this argument. Indeed, it is possible to deduce the existence of an extremal nonnegative biquadratic form that is not a sums-of-squares just from the fact that there exists any biquadratic form which is nonnegative but not sums-of-squares and general convex geometry.
Triquadratic forms and QFPMs
In analogy with the above relationship between linear maps between symmetric matrices and biquadratic forms, we can associate to each QFPM a triquadratic polynomial
$$ T(u,v,Y) = u^{\T}\Phi(vv^{\T}, Y)u. $$Again, there is a bijective relationship between triquadratic forms and quadratic families of linear maps between spaces of symmetric matrices. This polynomial is pointwise nonnegative exactly when $\Phi$ is a QFPM, and $\Phi$ is completely positive if and only if $T$ is a sum of squares.
There is a way to turn a general biquadratic form into a triquadratic one that preserves nonnegativity and the property of being a sum of squares. Given a biquadratic form $B : \R^{\ell} \times \R^k \rightarrow \R$, let $f : \R^n \times \R^m \rightarrow \R^{\ell}$ be a bilinear map. Then $B(f(u,v), y)$ is a nonnegative triquadratic form.
For the purposes of the construction below, we will consider the case in which $n = m$ and the bilinear $f(u,v) = u_0 v' - v_0 u'$, where $u = (u_0, u')$ and $v = (v_0, v')$. In particular, there is a QFPM $\Phi$ that is associated to the triquadratic form obtained by composing the Choi-Lam form with this bilinear map, and this is precisely the $\Phi$ that the OpenAI paper shows leads to a nonspectrahedral hyperbolicity cone.
Note that more general bilinear maps $f$ and indeed triquadratic maps $T$ that do not arise in this way could be used to obtain more general classes of nonspectrahedral hyperbolicity cones, but we will focus on these cases for simplicity.
A Nonspectrahedral Hyperbolicity Cone
Theorem 3
Let $B : \R^{m-1} \times \R^{k}\rightarrow \R$ be an extremal nonnegative biquadratic form that is not a sum of squares. Let $u = \begin{pmatrix}u_0\\u'\end{pmatrix}$ and $v = \begin{pmatrix}v_0\\v'\end{pmatrix}$, and let $\Phi$ be the QFPM associated to the nonnegative triquadratic form
$$ T(u,v,Y) = B(u_0 v' - v_0 u', Y). $$Then the convex cone $H_{\Phi}$ is not spectrahedral.
Click to expand the proof
We first record the consequence of extremality of $B$ that will be used at the end of the proof.
Lemma
If $\ell(z, Y)$ is any bilinear form satisfying
$$ \ell(z, Y)^2 \leq B(z, Y) \qquad \text{for all }(z, Y)\in \R^{m-1}\times \R^{k}, $$then $\ell=0$.
Click to expand the proof
expresses $B$ as a sum of two nonnegative biquadratic forms. Since $B$ spans an extreme ray of the cone of nonnegative biquadratic forms, there is some $\alpha\in[0,1]$ such that
$$ \ell^2=\alpha B. $$If $\alpha>0$, then
$$ B=\alpha^{-1}\ell^2, $$so $B$ is a sum of squares, contrary to assumption. Hence $\alpha=0$, and therefore $\ell=0$. Thus
$$ \begin{equation} \label{eq:weak-extremality} \ell^2\leq B \quad\Longrightarrow\quad \ell=0. \end{equation} $$$\Box$
Now suppose, for contradiction, that $H_\Phi$ is spectrahedral. We will show the following:
Lemma
If $Y \in \R^k$, $v \in \R^n$ and $u \in \R^m$ are unit vectors, then
$$ \begin{equation} \label{eq:B-norm} T(u, v, Y) = \left\|P(v)F(Y)R(u)\right\|_{\op}^2, \end{equation} $$where $P(v)$ denotes the orthogonal projection onto $\ker E(vv^{\intercal})$ and $R(u)$ denotes the orthogonal projection onto $\ker G(uu^{\intercal})$.
Click to expand the proof
Theorem 2 implies that there exist positive unital maps $E: \S^n \rightarrow \S^{n'}$, $G : \S^m \rightarrow \S^{m'}$ and a linear map $F : \R^k \rightarrow \R^{n' \times m'}$ so that
$$ \begin{equation} \label{eq:block-equivalence} Z\succeq\Phi(X^{-1}, Y) \Longleftrightarrow \begin{pmatrix} E(X) & F(Y)\\ F(Y)^{\T} & G(Z) \end{pmatrix} \succeq 0. \end{equation} $$Since $E$ is positive and unital, $E(X)\succ 0$ whenever $X\succ 0$. Thus, taking the Schur complement of $E(X)$, we obtain the equivalent formulation
$$ \begin{equation} \label{eq:schur-equivalence} Z\succeq\Phi(X^{-1}, Y) \quad\Longleftrightarrow\quad G(Z)\succeq F(Y)^{\T} E(X)^{-1}F(Y). \end{equation} $$We now consider what happens when we allow $X$ and $Z$ to both degenerate to rank one matrices. Fix unit vectors $v\in\R^n$ and $u\in\R^m$ and fix $Y\in\R^{k}$. For $t\geq1$, define
$$ X_t := vv^{\T}+t(I-vv^{\T}), \qquad Z_t := uu^{\T}+t(I-uu^{\T}). $$We see that for $t \ge 1$,
$$ X_t\succeq I, \qquad Z_t\succeq I. $$Positivity and unitality of $E$ and $G$ therefore imply
$$ E(X_t)\succeq I, \qquad G(Z_t)\succeq I, $$so both matrices are positive definite.
Define $r_t$ for each $t$ to be the minimum value so that $r_t Z_t \succeq \Phi(X_t^{-1}, Y)$, and note that there are two equivalent ways to compute the value of $r_t$ for a given $t$: one coming from the definition of $H_{\Phi}$ and one from its purported spectrahedral characterization.
$$ \begin{equation} \label{eq:threshold-equivalence} r_t Z_t\succeq\Phi(X_t^{-1}, Y) \quad\Longleftrightarrow\quad r_tG(Z_t) \succeq F(Y)^{\T} E(X_t)^{-1}F(Y). \end{equation} $$We want to compute the value of $\lim_{t\rightarrow \infty} r_t$ using these two equivalent characterizations. Considering the characterization of $r_t$ coming from the definition of $H_{\Phi}$, we can obtain the following:
Lemma
$$\lim_{t\rightarrow \infty} r_t = T(u,v,Y).$$
Click to expand the proof
Since $\Phi(\cdot, Y)$ is positive and $X_t^{-1}\succeq0$, we have $M_t\succeq0$. Congruence by $Z_t^{-1/2}$ gives
$$ r_tZ_t\succeq\Phi(X_t^{-1}, Y) \quad\Longleftrightarrow\quad r_tI\succeq M_t, $$so $r_t = \lambda_{\max}(M_t)$.
The matrices $X_t$ and $Z_t$ were chosen precisely so that their inverses collapse onto the rank-one directions $v$ and $u$. Indeed,
$$ X_t^{-1} = vv^{\T}+t^{-1}(I-vv^{\T}), $$and
$$ Z_t^{-1/2} = uu^{\T}+t^{-1/2}(I-uu^{\T}). $$Consequently
$$ X_t^{-1}\longrightarrow vv^{\T}, \qquad Z_t^{-1/2}\longrightarrow uu^{\T}. $$By linearity and continuity of $\Phi(\cdot, Y)$,
$$ \begin{align*} M_t &= Z_t^{-1/2} \Phi(X_t^{-1}, Y) Z_t^{-1/2} \\ &\longrightarrow uu^{\T}\Phi(vv^{\T}, Y)uu^{\T} = T(u,v,Y) uu^{\T}. \end{align*} $$Continuity of the largest eigenvalue yields
$$ \begin{equation} \label{eq:left-rank-one-limit} \lambda_{\max}(M_t) \longrightarrow T(u,v,Y). \end{equation} $$$\Box$
On the other hand, we will compute $\lim_{t\rightarrow \infty} r_t$ using the purported spectrahedral definition of $H_{\Phi}$.
Lemma
$$\lim_{t\rightarrow \infty} r_t = \left\|P(v)F(Y)R(u)\right\|_{\op}^2,$$where $P(v)$ is the orthogonal projection onto the kernel of $E(vv^{\intercal})$ and $R(u)$ is the orthogonal projection onto the kernel of $G(uu^{\intercal})$.
Click to expand the proof
Starting with the characterization
$$ r_tG(Z_t) \succeq F(Y)^{\T} E(X_t)^{-1}F(Y),$$we apply a congruence transformation by $G(Z_t)^{-1/2}$ to get
$$ \begin{align*} r_tG(Z_t) &\succeq F(Y)^{\T} E(X_t)^{-1}F(Y) \\ &\Longleftrightarrow\quad r_tI \succeq G(Z_t)^{-1/2} F(Y)^{\T} E(X_t)^{-1}F(Y) G(Z_t)^{-1/2} \\ &\Longleftrightarrow\quad r_tI\succeq C_t^{\T} C_t, \end{align*} $$where
$$ C_t := E(X_t)^{-1/2}F(Y)G(Z_t)^{-1/2}. $$The largest eigenvalue of $C_t^{\T} C_t$ is $\|C_t\|_{\op}^2$, so
$$ r_t = \|C_t\|_{\op}^2. $$We will now take $t\rightarrow \infty$. We will make use of the following fact: for any fixed positive semidefinite matrix $H$,
$$ \begin{equation} \label{eq:kernel-projection-limit} \lim_{t\rightarrow \infty} [I+(t-1)H]^{-1/2} = \proj_{\ker H}, \end{equation} $$where $\proj_{\ker H}$ denotes the orthogonal projection onto the kernel of $H$.
Applying this to $E(X_t)$ and $G(Z_t)$ and using unitality yields
$$ \lim_{t\rightarrow \infty} E(X_t)^{-1/2} = P(v) \qquad \lim_{t\rightarrow \infty} G(Z_t)^{-1/2} = R(u), $$where $P(v)$ and $R(u)$ are the orthogonal projections onto the kernels of $E(vv^{\intercal})$ and $G(uu^{\intercal})$ respectively.
$\Box$
By combining these characterizations of $\lim_{t\rightarrow \infty}r_t$, we arrive at the lemma.
$\Box$
With this lemma in mind, we now linearize \eqref{eq:B-norm} along the diagonal $u=v$. Fix
$$ v=e_0= \begin{pmatrix} 1\\0 \end{pmatrix}\in\R\times\R^{m-1}. $$For $z\in\R^{m-1}$, choose a smooth curve $u(t)$ on the unit sphere such that
$$ u(0)=e_0, \qquad \dot u(0)= \begin{pmatrix} 0\\z \end{pmatrix}. $$Then
$$ u_0(t)v'-v_0u'(t) = -tz+O(t^2). $$Since $B$ is quadratic in its first argument,
$$ \begin{equation} \label{eq:B-expansion} B(u_0(t)v'-v_0u'(t), Y) = t^2 B(z, Y)+o(t^2). \end{equation} $$On the other hand, setting $u=v=e_0$ in \eqref{eq:B-norm} gives
$$ \left\|P(e_0)F(Y)R(e_0)\right\|_{\op}^2 = B(0, Y)=0, $$and hence
$$ P(e_0)F(Y)R(e_0)=0. $$Differentiating the matrix-valued expression $P(e_0)F(Y)R(u(t))$ at $t=0$, we obtain a matrix-valued map
$$ \Psi(z, Y) := P(e_0)F(Y) \left. \frac{d}{dt}R(u(t)) \right|_{t=0}. $$The derivative of $R(u)$ depends linearly on the tangent vector $z$, while $F(Y)$ is linear in $Y$. Consequently $\Psi(z, Y)$ is bilinear in $(z, Y)$. Moreover,
$$ P(e_0)F(Y)R(u(t)) = t\Psi(z, Y)+o(t). $$Dividing \eqref{eq:B-norm} by $t^2$ and letting $t\to0$, using \eqref{eq:B-expansion}, yields
$$ \begin{equation} \label{eq:F-norm} B(z, Y)=\|\Psi(z, Y)\|_{\op}^2 \qquad \text{for all }z\in\R^{m-1},\ Y\in\R^{k}. \end{equation} $$Write the matrix entries of $\Psi$ as
$$ \Psi(z, Y)=\big(\ell_{ij}(z, Y)\big)_{i,j}. $$Each $\ell_{ij}$ is a bilinear form. Since the absolute value of every matrix entry is bounded by the operator norm,
$$ \ell_{ij}(z, Y)^2 \leq \|\Psi(z, Y)\|_{\op}^2 = B(z, Y). $$By \eqref{eq:weak-extremality}, it follows that $\ell_{ij}=0$ for every $i,j$. Hence $\Psi\equiv0$. Equation \eqref{eq:F-norm} then implies $B\equiv0$, contradicting the assumption that $B$ is a nonzero extremal nonnegative biquadratic form which is not a sum of squares.
Therefore $H_\Phi$ cannot be spectrahedral.
$\Box$
References
- J. W. Helton and V. Vinnikov. Linear matrix inequality representation of sets. Communications on Pure and Applied Mathematics, vol. 60, no. 5, pp. 654–674 (2007)
- V. Vinnikov. LMI representations of convex semialgebraic sets and determinantal representations of algebraic hypersurfaces: past, present, and future. Mathematical Methods in Systems, Optimization, and Control, Operator Theory: Advances and Applications, vol. 222, pp. 325–349 (2012)
- T. Netzer and R. Sanyal. Smooth hyperbolicity cones are spectrahedral shadows. Mathematical Programming, vol. 153, no. 1, pp. 213–221 (2015)
- V. Paulsen. Completely Bounded Maps and Operator Algebras. Cambridge Studies in Advanced Mathematics 78, Cambridge University Press (2002)
- È. B. Vinberg. The theory of convex homogeneous cones. Transactions of the Moscow Mathematical Society, vol. 12, pp. 340–403 (1963)
- M.-D. Choi. Positive semidefinite biquadratic forms. Linear Algebra and its Applications, vol. 12, pp. 95–100 (1975)
- M.-D. Choi and T.-Y. Lam. Extremal positive semidefinite forms. Mathematische Annalen, vol. 231, pp. 1–18 (1977)
- OpenAI. A counterexample to the generalized Lax conjecture. Preprint (2026). Add the canonical URL or DOI once the preprint is public