Exact-arithmetic construction and facial decomposition of pseudo-moment certificates for positive non-SOS forms

A homogeneous polynomial (form) that is positive on R^n but is not a sum of squares (SOS) can be certified as non-SOS in exact arithmetic by a pseudo-moment certificate: a linear functional, encoded by a positive semidefinite moment matrix with rational entries, that is nonnegative on the SOS cone yet takes a negative value on the given form. Henrion (2025) constructed such rational certificates, and extreme rays of the dual pseudo-moment cone, for four classical positive non-SOS forms by exploiting symmetry, but the method has precise gaps: it could not produce a rank-10 certificate for the Reznick ternary octic (the smallest extreme-ray rank possible for ternary octics), it decomposed interior certificates into extreme rays only ad hoc — one decomposition requiring irrational endpoints — and the achievable extreme-ray ranks are classified only in a few low-dimensional cases. The problem is to build the systematic exact-arithmetic facial theory of pseudo-moment certificate cones: resolve the rank-10 Reznick octic case (construct a certificate or prove impossibility), give a systematic algorithm with correctness and finite-termination guarantees that decomposes interior pseudo-moment certificates into convex combinations of extreme rays in exact rational arithmetic, and extend constructive rank control beyond highly symmetric forms and beyond the settled classifications. Kang-Yang 2026, on the facial geometry of the pseudo-moment cone, gives a general extreme-ray decomposition algorithm for spectrahedral cones in stabilized floating-point arithmetic with no rational-output guarantee; it does not touch the Reznick octic and does not treat the interior certificates of positive non-SOS forms.

Background

A real form is a homogeneous polynomial $p$ of degree $2d$ in $n$ variables; it is called positive if $p(x)\ge 0$ for all $x\in\mathbb{R}^n$, and a sum of squares (SOS) if $p=\sum_i q_i(x)^2$ for real polynomials $q_i$. Every SOS form is positive, and by Hilbert's 1888 theorem the converse fails except in three families of $(n,2d)$ (binary forms, quadratics, and ternary quartics). The cones of positive forms $P_{n,2d}$ and SOS forms $\Sigma_{n,2d}$ are therefore distinct in general, with $\Sigma_{n,2d}\subsetneq P_{n,2d}$; the Motzkin sextic and the Reznick octic $p_8(x_1,x_2,x_3)=x_1^2x_3^6+x_2^2x_3^6+x_1^4x_2^4-3x_1^2x_2^2x_3^4$ (Reznick 1978) are classical members of the gap.

By convex duality, a form $p\in P_{n,2d}\setminus\Sigma_{n,2d}$ can be separated from the closed convex cone $\Sigma_{n,2d}$ by a linear functional $\ell_y$ acting on coefficients, and membership of $\ell_y$ in the dual cone $\Sigma^*_{n,2d}$ (the pseudo-moment cone) is equivalent, via the Riesz/Haviland-type identification of functionals with truncated moment sequences $y$, to positive semidefiniteness of the moment matrix $M_d(y)=[\ell_y(v_iv_j)]$ built on a basis $\{v_i\}$ of the degree-$d$ forms. Such a $y$ with $\ell_y(p)<0$ is a pseudo-moment certificate of non-SOSness; when $y$ has integer or rational entries, the certificate is verifiable without error, since $M_d(y)\succeq 0$ reduces to nonnegativity of all principal minors and $\ell_y(p)<0$ to one exact evaluation. In the standard monomial basis $M_d(y)$ is a Hankel-type matrix (its entries repeat along antidiagonals), so $\Sigma^*_{n,2d}$ is also studied as a Hankel spectrahedron cone; a spectrahedron is a convex set defined by a linear matrix inequality, that is, by positive semidefiniteness of an affine family of symmetric matrices, and a cone so described is called spectrahedral.

The facial structure of $\Sigma^*_{n,2d}$ is organized by extreme rays (rays that cannot be written as a nontrivial sum of two directions in the cone); the rank of a pseudo-moment vector is the rank of its moment matrix. Blekherman (2012) compared the dual cones of $P$ and $\Sigma$ and, via positive Gorenstein ideals (graded ideals whose quotient algebra is self-dual, a structure exploited by Blekherman (2015) to construct extreme rays) and the algebraic boundaries of Hilbert's SOS cones (Blekherman, Hauenstein, Ottem, Ranestad, Sturmfels 2012), obtained sharp rank thresholds for non-evaluation extreme rays; Blekherman and Sinn (2017) settled the ternary case: extreme rays of $\Sigma^*_{3,2d}\setminus P^*_{3,2d}$ have rank $r\ge 3d-2$ (and $r\le\binom{d+2}{2}-4$ for $d\ge 4$), with exact spectra known for sextics ($r=7$), octics ($r=10$ or $11$), decics ($13\le r\le 17$), dodecics ($r=16$ or $18\le r\le 24$), and $\Sigma^*_{4,4}\setminus P^*_{4,4}$ ($r=6$). Beyond these cases the achievable ranks are not classified.

Henrion (2025) gave constructive procedures for rational pseudo-moment certificates: when $p$ is invariant under a finite group acting on the variables, the certificate search restricts to invariant functionals parametrized by a few orbit parameters (9 for the Reznick octic, 5 for the Choi-Lam quartic), turning $\Sigma^*$-membership into a low-dimensional spectrahedral cone $K_p$ that can be searched analytically for rational points. This yielded integer extreme rays for the Robinson and Motzkin ternary sextics (rank 7) and the Reznick ternary octic (rank 11, with ranks 11 through 15 attainable while certificates in $K_8$ have ranks in $\{10,\dots,15\}$), and rank-6 integer extreme rays for the Choi-Lam quaternary quartic $p_{CL}=x_1^2x_2^2+x_2^2x_3^2+x_1^2x_3^2+x_4^4-4x_1x_2x_3x_4$. Two limitations are explicitly recorded. First, the method never produced a rank-10 certificate for the Reznick octic, although rank-10 extreme rays of $\Sigma^*_{3,8}$ exist by the Blekherman-Sinn classification (they arise from other forms in $P_{3,8}\setminus\Sigma_{3,8}$). Second, interior (full-rank or higher-rank) certificates were decomposed into convex combinations of rank-deficient extreme rays only in an ad hoc way: for the Choi-Lam quartic, the rank-7 certificate with orbit parameters $(a,b,c,d,e)=(4,11,1,4,2)$ splits rationally into two rank-6 extreme rays, but the rank-9 certificate $(1,23,2,3,2)$ splits only into endpoints involving $\sqrt{2}$; the paper states that computing these decompositions systematically in rational or numerically stable arithmetic is an open research direction, a natural extension of the classical flatness-based solution-extraction step of moment-SOS hierarchies, where flatness means that the rank of the moment matrix stops growing when the truncation degree is raised, allowing the underlying atoms to be recovered (Henrion and Lasserre 2005). More broadly, the constructions lean on large symmetry groups: the certificate structure degrades as the symmetry group shrinks (Robinson versus Motzkin), and for fully symmetric even ternary octics every positive form is SOS, so no certificate exists at all — leaving forms with little or no symmetry, and degrees/variable counts beyond the classified cases, outside the method's reach.

Problem Statement

The common objective is to turn the ad hoc symmetry-based constructions of exact pseudo-moment certificates into a systematic constructive theory, in exact (rational) arithmetic, of the facial structure of pseudo-moment certificate cones, with the following jointly supporting deliverables:

1. Rank-10 certificates for the Reznick ternary octic. Either construct a pseudo-moment certificate $y\in K_8$ (the 9-parameter invariant spectrahedral cone $K_8$ for $p_8$, introduced in the source's Section 5) with rational entries for $p_8=x_1^2x_3^6+x_2^2x_3^6+x_1^4x_2^4-3x_1^2x_2^2x_3^4$ whose degree-4 moment matrix $M_4(y)$ has rank exactly 10 — which would match the Blekherman-Sinn lower bound $r\ge 3d-2=10$ on the rank of an extreme ray of $\Sigma^*_{3,8}\setminus P^*_{3,8}$, giving a minimal-rank pseudo-moment certificate that $p_8$ is not SOS, with extremality of the resulting ray separately checkable by an exact kernel test — or prove that no rank-10 element exists in the certificate cone $K_8$ (a statement about the symmetry-reduced invariant cone $K_8$ alone, which does not by itself exclude a non-invariant rank-10 certificate in the full cone $\Sigma^*_{3,8}$).

2. Systematic facial decomposition in exact arithmetic. Give an algorithm, with proven correctness and finite termination, that takes as input an interior pseudo-moment certificate of a positive non-SOS form (for instance the Choi-Lam rank-9 certificate with orbit parameters $(a,b,c,d,e)=(1,23,2,3,2)$, whose currently known decomposition into two rank-6 extreme rays requires irrational endpoints) and outputs an explicit convex combination of extreme rays of the pseudo-moment cone with exact rational data, or proves that no such rational decomposition exists; demonstrate it on the benchmark interior certificates of the source. The algorithm must specify the arithmetic regime (exact rational computation, or floating-point computation with certified exact rationalization of the output) under which its guarantees hold.

3. Constructive reach beyond high symmetry and settled classifications. Demonstrate the methodology on at least one positive non-SOS form with little or no symmetry, where the orbit-parameter reduction is weak, and additionally in at least one degree-variable setting $(n,2d)$ whose extreme-ray rank spectrum is not yet classified, thereby constructively extending the classification of achievable extreme-ray ranks beyond the settled cases (ternary sextics through dodecics, and $\Sigma^*_{4,4}$).

Deliverable 1 fixes the benchmark rank-minimality question left explicitly unresolved by the source's method; deliverable 2 is the systematic facial-decomposition procedure the source calls an interesting research direction; deliverable 3 measures the reach of the resulting theory beyond highly symmetric forms. They jointly support one objective: constructive, machine-verifiable control of the facial geometry of pseudo-moment cones in exact arithmetic. Note that complete rank classification in all degrees and variable counts is a long-term program; the completion boundary asked for here is the systematic constructive methodology with its guarantees, demonstrated on the stated benchmarks, not the exhaustion of the classification program.

References

1. Didier Henrion, "Positively not SOS: pseudo-moments and extreme rays in exact arithmetic", arXiv:2509.01382, 2025. DOI: 10.48550/arXiv.2509.01382, https://arxiv.org/abs/2509.01382
2. Shucheng Kang, Heng Yang, "Simplicial Regularizability of the Pseudo-Moment Cone and Carathéodory-Type Atomic Decomposition of Moment Matrices", arXiv:2605.06854, 2026. DOI: 10.48550/arxiv.2605.06854, https://arxiv.org/abs/2605.06854
3. Grigoriy Blekherman, Rainer Sinn, "Extreme rays of Hankel spectrahedra for ternary forms", Journal of Symbolic Computation 79:23-42, 2017. DOI: 10.1016/j.jsc.2016.08.003, https://doi.org/10.1016/j.jsc.2016.08.003
4. Grigoriy Blekherman, "Nonnegative polynomials and sums of squares", Journal of the American Mathematical Society 25(3):617-635, 2012. DOI: 10.1090/S0894-0347-2012-00733-4, https://doi.org/10.1090/S0894-0347-2012-00733-4
5. Grigoriy Blekherman, "Positive Gorenstein ideals", Proceedings of the American Mathematical Society 143(1):69-86, 2015. DOI: 10.1090/S0002-9939-2014-12253-2, https://doi.org/10.1090/S0002-9939-2014-12253-2
6. Grigoriy Blekherman, Jonathan Hauenstein, John Christian Ottem, Kristian Ranestad, Bernd Sturmfels, "Algebraic boundaries of Hilbert's SOS cones", Compositio Mathematica 148(6):1717-1735, 2012. DOI: 10.1112/s0010437x12000437, https://doi.org/10.1112/s0010437x12000437
7. Bruce Reznick, "Extremal PSD forms with few terms", Duke Mathematical Journal 45(2):363-374, 1978. DOI: 10.1215/s0012-7094-78-04519-2, https://doi.org/10.1215/s0012-7094-78-04519-2
8. Didier Henrion, Jean-Bernard Lasserre, "Detecting global optimality and extracting solutions in GloptiPoly", in D. Henrion, A. Garulli (eds.), Positive Polynomials in Control, Lecture Notes in Control and Information Sciences 312, Springer, 2005, pp. 293-310. DOI: 10.1007/10997703_15, https://doi.org/10.1007/10997703_15