PaperlayerView exact revision on arXiv

Source-linked AI summary

Explicit Separators for Consecutive Levels of Parrilo's Sum-of-Squares Hierarchy over the Copositive Cone

Jiachen Shen, Hui Zhong

arXiv:2608.27743v1eess.SY

TL;DR

The paper addresses the lack of explicit witnesses separating consecutive levels of Parrilo’s copositive SOS hierarchy beyond the first step. It constructs rational Horn-matrix scalings shifted along interior directions, proving the next three separations with exact certificates. These establish three strict inclusions, robust first-gap separation, and strict adjacent steps at arbitrarily large levels.

  • Problem

    For n=5, consecutive Parrilo hierarchy levels were not known to differ explicitly beyond the classical first step, despite convergence to COP_5 without finite-level exactness.

  • Method

    The paper shifts diagonal scalings of the Horn matrix along positive interior directions and certifies membership with rational Gram matrices and exclusion with rational dual moment functionals.

  • Results

    The paper proves K(1)_5⊊K(2)_5⊊K(3)_5⊊K(4)_5, with exact integer-arithmetic re-verification, and shows strict adjacent steps recur at arbitrarily large levels.

  • Takeaways & Limitations

    The threshold ε_r(M) provides a common device for locating separator windows, while the first gap is full-dimensional and the chain never stabilizes.

  • Takeaways & Limitations

    The unbounded recurrence result is non-constructive: it names neither the scaling nor the level, and may leave gaps among the strict indices.

Abstract

from arXiv · show

Parrilo's cones $\Kc{n}{r}$ form a nested sequence of semidefinite-representable inner approximations of the copositive cone $\COP_n$. For $n=5$ their union is all of $\COP_5$, yet no single level attains it, and whether consecutive levels actually differ had remained open beyond the classical first step. No explicit matrix in $\Kc{n}{t}\setminus\Kc{n}{t-1}$ had, to our knowledge, been published for any $t\ge2$ and $n\ge5$. We settle the first three cases. Explicit rational matrices, obtained from diagonal scalings of the Horn matrix shifted along a positive interior direction, lie in $\Kc{5}{2}\setminus\Kc{5}{1}$, in $\Kc{5}{3}\setminus\Kc{5}{2}$, and in $\Kc{5}{4}\setminus\Kc{5}{3}$, giving three consecutive strict inclusions $\Kc{5}{1}\subsetneq\Kc{5}{2}\subsetneq\Kc{5}{3}\subsetneq\Kc{5}{4}$. Each is certified by an exact rational Gram matrix and an exact rational dual moment functional, re-verified by a standalone program in integer arithmetic. The separations are robust. One fixed certificate pair covers an interval of shifts of width exceeding $3\cdot10^{-3}$, and $\Kc{5}{2}\setminus\Kc{5}{1}$ has nonempty interior. Combining a scaling theorem of Dickinson, Dür, Gijben and Hildebrand with the completeness theorem of Schweighofer and Vargas shows further that strict adjacent inclusions recur at arbitrarily large levels. All separators were located by one threshold device: the least shift $\eps_r(M)$ carrying $M$ into $\Kc{5}{r}$ along an interior direction is nonincreasing in $r$, and each strict drop between levels marks a window of separators.

1 Introduction

The paper addresses the previously unresolved strictness of consecutive Parrilo hierarchy levels for n=5. It gives explicit rational separators for the next three steps, exact certificates, a threshold-based search method, and an unbounded recurrence result.

  • Open problem: For n=5, the paper asks whether each consecutive inclusion in Parrilo’s hierarchy is strict, beyond the classical first separation.The hierarchy converges to COP_5, but no finite level equals it.
  • Certification: Each separator is certified by a rational Gram matrix for membership and a rational moment functional for exclusion, with exact integer-arithmetic re-verification.The certificates reduce the claims to finite rational identities and semidefiniteness checks.
  • Main results: The paper supplies explicit rational witnesses in K(2)_5\K(1)_5, K(3)_5\K(2)_5, and K(4)_5\K(3)_5.These establish three consecutive strict inclusions.
  • Further structure: The first gap is full-dimensional, while combining two prior theorems shows strict adjacent steps recur at arbitrarily large levels.A fixed certificate pair covers a shift interval, and the chain never stabilizes.
  • Search method: The threshold ε_r(M) is computable by one semidefinite program per level, nonincreasing in r, and strict drops identify separator windows.All witnesses were located with this one-dimensional device.

3 An explicit separator for the first open pair

The first open pair is separated by shifting a diagonally scaled Horn matrix along the all-ones direction. A rational Gram certificate proves level-two membership, while a rational moment functional proves exclusion from level one.

  • Exclusion certificate: A rational moment functional pairs negatively with M*, certifying M* ∉ K(1)_5.Its moment matrix is positive semidefinite, so the exclusion follows from the dual certificate lemma.
  • Construction: M* = DHD + 1/300 J lies in K(2)_5\K(1)_5 for D = diag(1/4,4,1,1,1).The scaling is chosen to violate the level-one criterion, and the shift moves the matrix into a certifiable interior region.
  • Membership certificate: A rational block Gram matrix establishes M* ∈ K(2)_5 through an exact sum-of-squares identity.Its blocks are positive semidefinite and checked by exact LDL^T decomposition.
  • Certificate structure: Coefficientwise certification fails at order two because irreducible cancellation occurs in off-diagonal Gram blocks.Genuine sums-of-squares certificates are therefore needed for this separator.
  • Robustness: The shift 1/300 is not finely tuned: the same certificate pair works over an interval of width exceeding 3·10^-3.The certificates deform explicitly throughout the interval.

4 The second pair

A more extreme Horn scaling yields a second explicit separator: a shifted matrix lies in K(3)_5 but outside K(2)_5. Exact Gram and moment certificates verify both sides of the separation.

  • General pattern: The second separation repeats the shift-and-certify pattern one level higher rather than relying on a level-one-specific phenomenon.The paper uses this repetition to motivate threshold analysis across levels.
  • Membership certificate: A rational block Gram matrix with positive semidefinite blocks proves M′ ∈ K(3)_5.The certificate is indexed by the degree-five monomials and respects the parity-class decomposition.
  • Why a new scaling: The first separator’s scaling cannot separate the second pair because its second-level threshold vanishes numerically.A more extreme scaling is therefore necessary for the second separation.
  • Exclusion certificate: A rational exclusion certificate confirms M′ ∉ K(2)_5, and the same construction shows M′ is copositive.Thus the certificate also supplies an exact witness for K(2)_5 = COP_5.

5 The third pair

The third separator uses a rank-one interior direction adapted to the Horn form’s zeros because the all-ones window is too narrow for manageable rational recovery. Exact certificates place the matrix in K(4)_5 and exclude it from K(3)_5.

  • Membership certificate: A rational block Gram matrix with positive semidefinite blocks proves M′′ ∈ K(4)_5.The matrix is indexed by degree-six monomials and decomposes across 16 even-parity classes.
  • Certificate construction: The membership Gram is formed by reserving part of the shift and adding a positive coefficient-diagonal Gram.This produces an exact Gram for the shifted polynomial over the rationals.
  • Arithmetic conditioning: The all-ones window is too thin for manageable rational denominators, so the adapted rank-one direction provides the workable third-pair certificate.The direction changes the arithmetic conditioning without changing the shift-and-certify strategy.
  • Interior direction: The rank-one direction dd^T equalizes its shift polynomial at the five minimal zeros of the Horn form.This choice conditions both the membership and exclusion certificates.

6 The J-threshold device

The paper introduces a threshold profile measuring the least shift into each Parrilo cone level, then uses strict drops to locate separator windows. Positive directions such as J are interior to every level, making the thresholds finite and monotone.

  • Interior directions: J lies in the interior of every K(r) because its associated polynomial has a diagonal Gram matrix with strictly positive entries.The same construction extends to positive diagonal scalings of entrywise-positive matrices, including rank-one directions dd⊤.
  • Threshold definition: The threshold ε_r(M) is the least nonnegative shift such that M + εJ enters K(r), and its feasible shifts form [ε_r(M), ∞).The threshold is attained and finite for every symmetric M.
  • Search principle: ε_r+1(M) ≤ ε_r(M), and every strict drop produces a window of shifts separating consecutive levels.For shifts above the higher-level threshold, membership follows from nesting and addition of the interior direction.
  • Computation: Each threshold is computed by one semidefinite program, introducing ε as a nonnegative variable while retaining linear coefficient constraints.This reduces the search over S5 to comparing scalar profiles across levels.
  • Direction choice: The usable separator window depends strongly on the interior direction: flat shifts along J preserve a workable margin, whereas identity shifts close the window almost immediately.The paper leaves the best direction in general as an open question.

7 A one-parameter family of separators

A one-parameter family obtained by shifting a scaled Horn matrix along J contains certified separators between the first two levels. The separation is robust: it includes an explicit interval and a full-dimensional open neighborhood.

  • Exclusion certificate: A fixed dual functional excludes the same shifted matrices from K(1) throughout the certified interval.Thus the family gives a continuous interval of explicit separators rather than a single numerically located point.
  • Certified interval: For every ε with 1/10000 < ε < 9981109/2994257024 ≈ 3.3334 · 10^-3, M0 + εJ lies in the interior of K(2).The lower endpoint is εlo = 1/10000 and the upper endpoint is ε* = 9981109/2994257024.
  • Full-dimensional gap: The gap K(2) \ K(1) contains an open Frobenius ball around an explicit point, so it has nonempty interior of full dimension.The perturbation proof preserves positive semidefiniteness on the membership side and negativity of the exclusion pairing.
  • Stability: The construction is certified by an explicit rational Gram assignment whose positive definiteness survives sufficiently small symmetric perturbations.The paper notes that the resulting radius is positive but pessimistic, while the long thin separator slab along J is more informative geometrically.

8 Strict steps at arbitrarily large levels

Combining a scaling theorem with the completeness of the hierarchy shows that strict adjacent inclusions recur at arbitrarily large levels. The result is non-constructive and does not identify every level.

  • Unbounded recurrence: For every R ∈ N, there exist s > R and a diagonal scaling D such that DHD lies in K(s) \ K(s−1).This yields strict adjacent steps beyond every prescribed level.
  • Consequence: The chain contains infinitely many strict inclusions between consecutive members.This establishes recurrence without determining where every strict step occurs.
  • Proof strategy: The argument uses Dickinson, Dür, Gijben and Hildebrand to place a scaling outside K(R), then Schweighofer and Vargas to place it in some finite level.Minimality of that finite level produces the adjacent separation.
  • Scope: The theorem is non-constructive twice over: it names neither the scaling nor the level, and the resulting strict indices may leave gaps.Whether every positive entry level is attained remains open; the first three cases are settled explicitly elsewhere.

9 Closed-form separators in the coefficient hierarchy

The coefficient hierarchy admits explicit closed-form separators: a fixed Horn scaling yields seven consecutive strict separations, certified by finite coefficient lists rather than semidefinite programs.

  • The coefficient cones replace sum-of-squares conditions with nonnegative coefficients, making membership decidable by inspecting finite coefficient lists.This hierarchy is an elementary shadow of the semidefinite hierarchy and provides explicit low-level certificates.
  • The threshold εr(M) is determined by the most negative normalized coefficient and is a rational number computable in closed form.The coefficient calculation reduces to finitely many monomials of degree 2r + 4.
  • For the fixed scaling in Theorem 9.2, εr(M) decreases strictly for 1 ≤ r ≤ 8, producing seven consecutive coefficient-cone separations.Each strict drop yields a window of separators between consecutive levels.
  • The closed form εr(M) = (16 − r)/(r + 2) holds on the stated range but fails beyond r = 8 when the maximizing monomial changes.There is no strict drop between the eighth and ninth cones, although thresholds resume decreasing later.
  • The coefficient hierarchy separates more easily than the sum-of-squares hierarchy because its cones are smaller and its certificates are read directly from coefficient lists.Thus coefficient-cone separators need not separate the corresponding semidefinite cones.

10 A second orbit: the T (ψ) matrices

The separator construction extends from the Horn matrix to a second exceptional copositive orbit generated by trigonometric matrices T(ψ). A rational point on this orbit yields explicit coefficient and semidefinite separations.

  • The T(ψ) family is a second exceptional extreme-ray orbit of COP5 alongside diagonal scalings of the Horn matrix.The paper uses a rational point with all angles equal and cos θ = 9/10.
  • The rational circulant T lies in K(1)5 \ K(0)5, providing a second extreme matrix that realizes the classical first separation.Its shifted diagonal scaling then separates the next pair.
  • The coefficient hierarchy also separates along the T(ψ) orbit through an initial run of levels with closed-form thresholds.The maximizing monomials use triples of variables, unlike the pair-supported zeros of the Horn matrix.
  • The scaling MT = DTD + 1/1000J lies in K(2)5 \ K(1)5 with exact rational Gram and dual certificates.Both certificates are verified over Q by a standalone checker.
  • Using a disjoint extreme orbit shows that the semidefinite separations reflect the copositive boundary rather than properties unique to the Horn matrix.The same threshold device and interior shifts produce the certificates.

11 The threshold landscape

The threshold landscape maps where scaled Horn matrices enter successive cones and guides separator construction. Profiles are hump-shaped, deeper levels favor more extreme scalings, and level-four certification requires a better-conditioned rank-one direction.

  • The threshold profiles rise from zero at a membership boundary, peak, and return to zero as the scaling degenerates.This hump-shaped behavior occurs along both parameter paths.
  • The maximizer of ε1, ε2, and ε3 moves toward a = 1/8, a = 1/16, and a = 1/24, respectively, as the level deepens.More lopsided scalings are required to remain outside deeper cones.
  • Each of three measured profiles decreases strictly through r = 4, exposing candidate windows for separators in K(4)5 \ K(3)5.The all-ones direction produces narrow fourth-level windows, about 1.8 · 10−4 in the last row.
  • The fourth-level certificate uses the rank-one direction dd⊤, widening the window by an order of magnitude to approximately ε4 ≈ 1.5 · 10−4 and ε3 ≈ 1.8 · 10−3.This direction was selected because the all-ones windows were delicate to rationalize.
  • Near degeneration, solver outputs can violate the forced monotonicity ε3 ≤ ε2 because Gram blocks become ill-conditioned.The paper excludes the affected point from the numerical table, while its certified results remain unaffected.
  • The entry-level bands are exact for ι ∈ {1, 2}, while bands for ι = 3 and ι = 4 are only suggested numerically.The boundary between ι = 2 and ι ≥ 3 is not known in an exact level-two criterion.

12 Extracting exact certificates

The paper explains why exact certification fails on raw Horn scalings and how interior shifts, margin-maximizing objectives, and elementwise repair produce verifiable rational certificates.

  • Boundary obstruction: Raw positive diagonal scalings of the Horn matrix lie on the boundary of COP_5, forcing rank deficiency in every Gram certificate.The obstruction arises from five linearly independent evaluation vectors associated with minimal nonnegative zeros.
  • Boundary obstruction: Exact rational rounding fails on raw scalings because the feasible certificate set contains no positive definite point to round toward.Near-singular numerical Gram matrices acquire small negative eigenvalues after exact repair.
  • Interior shifting: Shifting along J moves targets into the interior of K(2)_5, where positive definite Gram matrices exist and rounding becomes routine.The usable shift window is narrow, with width about 10^-3, so thresholds guide its selection.
  • Certificate construction: Parity reduction splits the certificate variables into smaller blocks, while primal membership Grams and dual moment matrices certify adjacent-level separation.At level two, the Gram variable splits into one 15 × 15 block, ten 5 × 5 blocks, and five scalars; level three splits into five 15 × 15 blocks, ten 5 × 5 blocks, and one scalar.
  • Certificate construction: Maximizing the smallest eigenvalue returns well-centred Gram matrices with positive margin, enabling successful rational rounding at denominators of a few thousand.On interior targets, normalized margins were of order 10^-1.
  • Certificate construction: Elementwise exact repair reduces coefficient correction to division because each Gram-entry column contributes to one target monomial and AA^T is diagonal.This makes level-three repair with 126 basis monomials a matter of seconds rather than a dense rational solve.

13 Consequences for the stability-number bounds

The paper connects Parrilo-level cone strictness to stability-number bounds, using the five-cycle and Horn matrix as the motivating case while distinguishing geometric separation from an actual graph-bound improvement.

  • Stability-number bounds: Copositive relaxations produce stability-number bounds ϑ(r)(G) that decrease toward α(G), making hierarchy refinement relevant to graph optimization.The bounds are built by relaxing a copositive formulation of the stability number.
  • The five-cycle: For the five-cycle, the Horn matrix is the stability certificate obtained from λ(I + A_C5) − J at λ = 2.Because α(C5) = 2, this matrix is the central example for the hierarchy’s first strict step.
  • The five-cycle: The five-cycle is the smallest graph where SPN tightening fails and one Parrilo level repairs the gap.Here the level-zero and level-one bounds coincide with the strengthened and ordinary theta values, while H leaves SPN5 and enters K(1)_5.
  • Higher-order refinement: The explicit separators certify that the cones defining ϑ(1), ϑ(2), ϑ(3), and ϑ(4) are pairwise distinct.Thus geometric refinement is present at each of the first three higher-order steps.
  • Scope of the consequence: Cone strictness alone does not establish a graph whose stability bound improves between consecutive levels.A graph-bound gap requires a separator in the constrained affine form λ(I + A_G) − J, unlike the Horn scalings used here.

14 A quantum application

The paper maps dual certificates to explicit quantum states, showing that the first cone separation yields a rational PPT bound-entangled state with sharply characterized symmetric-extension behavior.

  • Cone–state correspondence: The dual cone correspondence maps K(r)_5^* to Dicke-diagonal states admitting m-party fully bosonic PPT extensions when m−2 corresponds to r.Entrywise nonnegative matrices give valid states, and positive semidefiniteness gives the PPT condition.
  • State construction: The dual certificate from Theorem 3.1 produces a matrix X that is entrywise nonnegative and positive semidefinite, but pairs negatively with M* ∈ K(2)_5.Exact verification checks X’s positivity properties and the negative pairing.
  • Extension separation: ρ(X) admits a three-party fully bosonic PPT symmetric extension but not a four-party one.This places the state between consecutive extension orders under the stated correspondence.
  • State construction: The resulting Dicke-diagonal state ρ(X) is a rational PPT bound-entangled state on C5 ⊗ C5 with Schmidt number two.Its entanglement follows from X not being completely positive, while its PPT property follows from X being doubly nonnegative.
  • Scope and outlook: The quantum interpretation does not by itself establish separation of consecutive orders in the ordinary PPT symmetric-extension hierarchy.That identification is described as expected on the two-boson sector and pursued in a companion paper.
  • Broader implications: The paper’s broader conclusion is that explicit rational separators exist for three consecutive hierarchy steps, with exact certificates and integer-arithmetic re-verification.The same threshold device also supports robustness, recurrence at arbitrarily large levels, and the quantum construction.

Appendix A Certificates for Theorem 3.1

The appendices provide exact rational membership and exclusion certificates for the paper’s separator matrices, together with an integer-arithmetic verifier that checks identities and positive semidefiniteness.

  • Certificate structure: The certificate matrices use rational Gram representations for membership and rational dual functionals for exclusion.The functionals are supported on monomials even in every variable, yielding parity-block moment matrices.
  • Certificate structure: The Gram matrices are block-diagonal across parity classes, with exact rational entries and archived full matrices.Reported block sizes include 15, 5, and 1, while the largest certificate uses degree-6 monomials and blocks of sizes 35, 15, and 5.
  • Exclusion certificates: The level-3 exclusion certificate has pairing ⟨y′′, c3(M′′)⟩ ≈ −0.001323, placing M′′ outside K(3)5.Its full 126 × 126 moment matrix is positive semidefinite, so the negative pairing certifies exclusion.
  • Verification: The standalone verifier reconstructs the matrices, expands polynomial identities, evaluates dual pairings, and tests positive semidefiniteness exactly.It uses only integer and rational arithmetic, rejects perturbed certificate data, and runs in seconds.
  • Verification: Positive semidefiniteness is decided over Q by symmetric Gaussian elimination with rational congruence and Schur-complement updates.The test returns true exactly when the input rational matrix is positive semidefinite.
Loading 2608.27743v1…