OctoInformBeta

Hyperbolicity cones without semidefinite lifts

For an integer m≥1m \ge 1, a homogeneous polynomial p∈ℝ[x1,…,xm]p \in \mathbb{R}[x_1, \dots, x_m] of degree d≥1d \ge 1 is hyperbolic with respect to e∈ℝme \in \mathbb{R}^m if p(e)≠0p(e) \ne 0 and every root of t↦p(te−x)t \mapsto p(te - x) is real for every x∈ℝmx \in \mathbb{R}^m. For such pp and ee, the closed hyperbolicity cone Λ+(p,e)\Lambda_+(p, e) is the set of points x∈ℝmx \in \mathbb{R}^m for which every root of t↦p(te−x)t \mapsto p(te - x) is nonnegative. For each integer N≥1N \ge 1, write Sym⁡N\operatorname{Sym}^N for the space of real symmetric N×NN \times N matrices. Let INI_N denote the N×NN \times N identity matrix. For A∈Sym⁡NA \in \operatorname{Sym}^N, write A≽0A \succeq 0 when AA is positive semidefinite. A cone K⊆ℝmK \subseteq \mathbb{R}^m is spectrahedral if there exist an integer N≥1N \ge 1 and a real linear map L:ℝm→Sym⁡NL : \mathbb{R}^m \to \operatorname{Sym}^N such that K={x∈ℝm:L(x)≽0}K = \{x \in \mathbb{R}^m : L(x) \succeq 0\}. The geometric Generalized Lax conjecture asserts that every closed hyperbolicity cone is spectrahedral.

Gårding established that closed hyperbolicity cones are convex. The original conjecture of Lax asks for a definite determinantal representation of homogeneous hyperbolic polynomials in three variables. Helton and Vinnikov proved the corresponding definite determinantal representation theorem. Lewis, Parrilo, and Ramana established its equivalence with Lax’s formulation. A real polynomial g∈ℝ[x1,…,xm]g \in \mathbb{R}[x_1, \dots, x_m] with g(0)=1g(0) = 1 is real-zero if the roots of s↦g(sx)s \mapsto g(sx) are real for every x∈ℝmx \in \mathbb{R}^m. In higher dimension, Brändén constructed a real-zero polynomial none of whose positive powers admits a definite determinantal representation. Kummer showed that the closed hyperbolicity cone of a polynomial can admit a 7×77 \times 7 spectrahedral representation even though no positive power of that polynomial has a definite determinantal representation. Raghavendra, Ryder, Srivastava, and Weitz proved exponential lower bounds on the matrix size of spectrahedral representations for suitable closed hyperbolicity cones. A homogeneous polynomial p∈ℝ[x1,…,xm]p \in \mathbb{R}[x_1, \dots, x_m] hyperbolic with respect to e∈ℝme \in \mathbb{R}^m is strictly hyperbolic if t↦p(te−x)t \mapsto p(te - x) has distinct roots whenever x∉ℝex \notin \mathbb{R}e. Kummer and Netzer proved that the closed hyperbolicity cones of strictly hyperbolic polynomials are spectrahedral. A spectrahedral shadow is a linear image of a set of the form {x∈ℝk:A0+L(x)≽0}\{x \in \mathbb{R}^k : A_0 + L(x) \succeq 0\} for integers k,N≥1k, N \ge 1, A0∈Sym⁡NA_0 \in \operatorname{Sym}^N, and a real linear map L:ℝk→Sym⁡NL : \mathbb{R}^k \to \operatorname{Sym}^N. Netzer and Sanyal proved that a closed hyperbolicity cone is a spectrahedral shadow when every nonzero boundary point is a smooth point of the defining polynomial. In version 1, González Nevado stated a positive solution of the geometric Generalized Lax conjecture.

For y=(y1,y2,y3)∈ℝ3y = (y_1, y_2, y_3) \in \mathbb{R}^3 with indices in {1,2,3}\{1, 2, 3\} read cyclically, define Q(y)∈Sym⁡3Q(y) \in \operatorname{Sym}^3 by Q(y)ii=yi2+yi+12Q(y)_{ii} = y_i^2 + y_{i+1}^2 and Q(y)ij=−yiyjQ(y)_{ij} = -y_i y_j for i≠ji \ne j. Given y∈ℝ3y \in \mathbb{R}^3, define the linear map Φy:Sym⁡4→Sym⁡4\Phi_y : \operatorname{Sym}^4 \to \operatorname{Sym}^4 on block matrices with a∈ℝa \in \mathbb{R}, r∈ℝ3r \in \mathbb{R}^3, and T∈Sym⁡3T \in \operatorname{Sym}^3 by Φy(ar⊤rT)=(tr⁡(Q(y)T)−r⊤Q(y)−Q(y)raQ(y))\Phi_y\begin{pmatrix} a & r^\top \\ r & T \end{pmatrix} = \begin{pmatrix} \operatorname{tr}(Q(y)T) & -r^\top Q(y) \\ -Q(y)r & aQ(y) \end{pmatrix}. For X∈Sym⁡4X \in \operatorname{Sym}^4, write adj⁡X\operatorname{adj} X for the adjugate of XX. At (X,Z,y)∈Sym⁡4×Sym⁡4×ℝ3(X, Z, y) \in \operatorname{Sym}^4 \times \operatorname{Sym}^4 \times \mathbb{R}^3, set p(X,Z,y)=det⁡((det⁡X)Z−Φy(adj⁡X))p(X, Z, y) = \det((\det X)Z - \Phi_y(\operatorname{adj} X)). Put e=(I4,I4,0)∈Sym⁡4×Sym⁡4×ℝ3e = (I_4, I_4, 0) \in \operatorname{Sym}^4 \times \operatorname{Sym}^4 \times \mathbb{R}^3. The preprint proves that pp is homogeneous of degree 2020 on the real space Sym⁡4×Sym⁡4×ℝ3\operatorname{Sym}^4 \times \operatorname{Sym}^4 \times \mathbb{R}^3 of dimension 2323, satisfies p(e)=1p(e) = 1, and is hyperbolic with respect to ee. Set K=Λ+(p,e)K = \Lambda_+(p, e). The closed hyperbolicity cone KK is not spectrahedral. The polynomial pp is not strictly hyperbolic. An assertion in version 1 of González Nevado is refuted. The preprint also derives a corollary that the Lean library does not contain: the quotient p/det⁡Xp / \det X extends to a homogeneous polynomial of degree 1616 on Sym⁡4×Sym⁡4×ℝ3\operatorname{Sym}^4 \times \operatorname{Sym}^4 \times \mathbb{R}^3 that equals 11 at ee, is hyperbolic with respect to ee, and has closed hyperbolicity cone KK.

The results on these pages are those of the Lean library, each stated as the Lean library states it and linked to the Lean declaration behind it. Lean has checked every result of the Lean library, so the Lean library is the reference. The preprint is a guide only, giving the results their order and their names. Where the preprint states a result differently, the statement on the page is the Lean library’s, with the preprint’s given beside it.

The Lean library: HyperbolicCones

HyperbolicCones is a Lean library: 17 items, in seven groups. Each has a page written by OctoInform, listed below.

§1. Introduction 4 items
  1. §1: Hyperbolicity, hyperbolicity cones, and spectrahedral cones Ambient matrix space and root-defined hyperbolicity cone.
  2. §1.1: The Choi-Lam form, positive map, and explicit polynomial Constructing the explicit polynomial from the Choi-Lam form.
  3. Theorem 1.1 An explicit polynomial with a nonspectrahedral hyperbolicity cone.
  4. §1.2: Failure of strict hyperbolicity Failure of strict hyperbolicity for a determinantal polynomial.
§2. A biquadratic form with no dominated square 1 item
  1. Lemma 2.1 The Choi-Lam form dominates no nonzero squared real bilinear form.
§3. Hyperbolicity and two cone slices 3 items
  1. §3: Rank-one identity (3.1), positivity, and scaling (3.2) Rank-one identity and quadratic scaling of Φy\Phi_y.
  2. Proposition 3.1 The determinantal polynomial is homogeneous and hyperbolic.
  3. Proposition 3.2 Semidefinite inequalities characterize two slices of a hyperbolicity cone.
§4. What a semidefinite representation would imply 2 items
  1. §4: Positive unital maps and normalized block pencils Positive unital maps and normalized block pencils.
  2. Proposition 4.1 Linear pencil representations of the hyperbolicity cone yield normalized pencils.
§5. Rank-one limits and a norm identity 2 items
  1. §5: Kernel projections P(v) and R(u) Left and right kernel projections of a normalized pencil.
  2. Proposition 5.1 Normalized pencils satisfy the Choi-Lam norm identity.
§6. The tangent obstruction (proof of Theorem 1.1) 3 items
  1. §6: Local constant-rank smooth extension of R(u) Kernel projections extend smoothly with constant rank near some point.
  2. §6: Tangent norm identity (6.1) Normalized pencils satisfy a Choi-Lam tangent norm identity.
  3. §6: Tangent isomorphism and contradiction Tangent obstruction proves the hyperbolicity cone KK is not spectrahedral.
Appendix A. A path-containment assertion 2 items
  1. Appendix A: Real-zero polynomials, rigidly convex sets, and the deformed quadratic Deformed univariate polynomials and rigidly convex sets.
  2. Appendix A (example): Failure of all-intermediate-times containment Smooth symmetric determinantal quadratic paths can fail intermediate containment.

No item matches.