{"id":"64471940-a5ef-4a98-948e-3fa0e22d70f3","arxiv_id":"1909.00569","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A sparse noncommutative Positivstellensatz and sparse GNS extraction are proved, giving converging SDP hierarchies for eigenvalue and trace optimization under a running-intersection sparsity pattern.","lead":"Optimizing polynomials in noncommuting variables gets a sparse treatment: the paper proves a sparse Positivstellensatz and a sparse GNS construction that yield converging semidefinite hierarchies for eigenvalue and trace problems. The benefit is that variable clusters satisfying a running intersection property give much smaller SDPs than the dense hierarchy, at the price of checking flatness and irreducibility when extracting exact optimizers.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.3's proof amalgamates over B(H(I1∩I2)) using embeddings ι_k that need not exist; the convergence corollaries rest on this step.","rationale":"The reader's RIP concern is valid but is primarily an applicability caveat: Example 3.4 already demonstrates that RIP is necessary. My concern is more immediate and technical: the proof of the main theorem contains a specific unjustified operator-algebraic step in the amalgamation construction. However, I do not think this refutes the theorem, because the common algebra can likely be replaced by the universal C*-algebra of the intersection variables; this is a standard repair. Thus the verdict remains CONDITIONAL: the paper should supply a corrected amalgamation argument. The numerical reproducibility issue identified by the reader is real but secondary to the theoretical core. I credit the paper with a coherent structure, a substantial nontrivial result, and an explicit counterexample showing that the sparse SOHS theorem fails; the concern here is about proof completeness, not fraud or internal inconsistency.","tokens_in":37144,"tokens_out":26972,"duration_ms":515994,"concrete_test":"Take p=2 with I1={1,2}, I2={2,3}, an archimedean S, and choose L on R⟨X2⟩ with L = (δ_0+δ_1)/2, so H12 is two-dimensional and the intersection algebra is the diagonal C*-algebra, not M2. Attempt to write an explicit state-preserving *-homomorphism ι_k: B(H12)=M2 → B(H(Ik)) satisfying ι_k(Â12_2)=Âk_2 for the GNS representations of L1 and L2. If no such ι_k exists, the printed proof is invalid. Then check whether replacing B(H12) by the universal C*-algebra generated by a self-adjoint u with ||u||≤1, setting ι_k(u)=Âk_2 and ⟨u^m⟩=L(X2^m), makes the amalgamation and the displayed equalities go through. A complete write-up of this replacement would settle whether Theorem 3.3 stands as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central convergence claims (Corollaries 5.9 and 6.6) rest on Theorem 3.3. In the p=2 case of its proof, the authors apply the amalgamation theorem with A = B(H(I1∩I2)) and 'canonical embeddings' ι_k: B(H(I1∩I2)) → B(H(Ik)) satisfying ι_k(Â12_i) = Âk_i. Such embeddings need not exist. The GNS space H12 for the intersection variables is a cyclic subspace of Hk on which Âk_i restricts to Â12_i, but the full operator Âk_i can behave arbitrarily on the orthogonal complement. For example, if the intersection algebra is diagonal 2×2 matrices, no unital *-homomorphism of M2 into B(Hk) sends the diagonal generator to the full operator Âk_i unless the complement is a matching representation. The parenthetical claim that B(H(I1∩I2)) contains the algebra generated by Â12_i as a dense subset is false in general: for L12 = (δ_a+δ_b)/2 on one variable, the generated algebra is the diagonal algebra, not M2. Without a common C*-algebra with state-preserving maps into each B(H(Ik)), the equality j1(Â1_i) = j2(Â2_i) used to define the amalgamated tuple A is unjustified. A likely repair is to amalgamate the universal C*-algebra generated by the intersection variables with u_i ↦ Âk_i; the moment functional L on the intersection defines a state on that universal algebra. But as printed, the proof has a gap at its load-bearing point, and the same issue recurs in the induction step and in the trace version Proposition 6.5.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the first systematic treatment of sparsity in noncommutative polynomial optimization. It states a sparse Positivstellensatz (Theorem 3.3) under the running intersection property (RIP), builds a sparse GNS construction for extracting optimizers (Theorem 4.2), and derives converging SDP hierarchies for eigenvalue optimization (Corollary 5.9) and trace optimization (Corollary 6.6). The sparse hierarchies have matrix sizes controlled by the cluster sizes rather than by the full number of variables. The paper also gives counterexamples showing that sparsity alone is not enough (Example 3.4) and that there is no sparse analog of the Helton–McCullough SOHS theorem (Lemma 5.2), and it reports numerical experiments with the NCSOStools implementation.","tokens_in":37470,"tokens_out":8504,"duration_ms":80056,"significance":"If correct, the sparse Positivstellensatz and the convergent hierarchies are a substantial advance: they extend the commutative sparse SOS theory of Lasserre and Waki et al. to a noncommutative setting where dense relaxations become intractable very quickly. The companion extraction results and the explicit counterexamples clarify the exact role of RIP and irreducibility. The paper is also careful to derive the sparse Positivstellensatz from the dense Helton–McCullough theorem and operator-algebraic amalgamation, with no fitted parameters. The main obstacle is a gap in the proof of the central Theorem 3.3 and a parallel gap in Proposition 6.5; these must be repaired before the convergence claims can be considered established.","major_comments":[{"comment":"The proof applies Theorem 3.1 with A = B(H(I1 ∩ I2)) and claims that there are 'canonical embeddings' ι_k : B(H(I1 ∩ I2)) → B(H(Ik)) satisfying ι_k(Â12_i) = Âk_i and that B(H(I1 ∩ I2)) contains the algebra generated by the Â12_i as a dense subset. Both assertions are false in general. For example, if I1 ∩ I2 = {1} and L12 makes X1 have two-point spectrum with H(I1 ∩ I2) two-dimensional, the algebra generated by Â12_1 is the diagonal algebra, not B(H(I1 ∩ I2)), so the density claim fails. Moreover, even when H(I1 ∩ I2) is a cyclic subspace of H(Ik), the operator Âk_i is block diagonal with respect to this subspace and its action on the complement is arbitrary; a unital *-homomorphism from B(H(I1 ∩ I2)) into B(H(Ik)) that sends Â12_i to Âk_i need not exist. Consequently, the equality j1(Â1_i) = j2(Â2_i) used to define the amalgamated tuple A is unjustified. The same defective step is invoked in the induction step for p > 2. Since Theorem 3.3 is the load-bearing input to Corollaries 5.9 and 6.6, the convergence claims are not yet supported. A likely repair is to amalgamate the universal C*-algebra generated by the intersection variables (with the state induced by L12) rather than the full B(H(I1 ∩ I2)).","section":"Section 3, proof of Theorem 3.3, p = 2 case"},{"comment":"The proof of the tracial sparse Positivstellensatz has the same amalgamation problem as Theorem 3.3. After the Hahn–Banach separation step, the GNS construction is said to yield operator algebras A_k and A_jk with tracial states, and then the proof simply says 'Now amalgamate in the category of von Neumann algebras'. No state-preserving (trace-preserving) embeddings of the intersection von Neumann algebra into each A_k are constructed, and without such embeddings the amalgamation theorem does not apply. The fact that the GNS representations of tracial states give finite von Neumann algebras does not by itself identify the intersection subalgebra inside each A_k in a way that makes the amalgamation possible. Since Corollary 6.6 depends on Proposition 6.5, this gap must also be closed.","section":"Section 6, proof of Proposition 6.5"},{"comment":"The proof of Theorem 4.2 is written out in detail only for p = 2, and the general case is dismissed with 'the general case then follows by a simple inductive argument'. This is not sufficient, especially because the hypotheses (H1) and (H2) are stated pairwise. For p > 2, one must show that the pairwise operator algebras A(Ij ∩ Ik) and the pairwise embeddings are compatible on triple intersections, and that the constructed amalgamated representation satisfies (4.3) on the sum of all R⟨X(Ij)⟩. As written, the extraction results for p > 2, including Algorithm 4.6 and Proposition 5.11/Corollary 5.13, are not fully established. This does not affect the convergence theorems directly, but it is a claimed contribution of the paper.","section":"Section 4, proof of Theorem 4.2"}],"minor_comments":[{"comment":"The numerical experiments are described only through aggregate SDP sizes and timings; no raw SDP data, solver tolerances, or scripts are provided. This makes the reported 'surprisingly' equal bounds in Table 2 difficult to audit. It would be helpful to state the solver precision settings and to make the implementation publicly available in a reproducible form.","section":"Section 7, Tables 1–3"},{"comment":"The instruction 'Compute an orthogonal P such that P^{-1}χ_k^i P = Â12_i' presupposes that the intersection algebra is the full matrix algebra; this is guaranteed only under (H2). The sentence should state explicitly that the line is executed only when (H2) has been verified.","section":"Algorithm 4.6, line 10"},{"comment":"The domain of the linear functional L is written as R⟨X(I1)⟩2d + ⋯ + R⟨X(Ip)⟩2d. Since the decomposition f = f1 + ⋯ + fp is not necessarily unique, the objective function ∑⟨Md(L,Ik), G_fk⟩ depends on the chosen Gram matrices G_fk. The text does not discuss this dependence or specify how the decomposition is fixed.","section":"Section 5.1, SDP (5.7)"},{"comment":"Reference [GdLL19] is listed as 'to appear'; it should be updated to the published version. Also, some numerical entries such as Example 5.10 are reported with many decimals but no provenance; a note on numerical rounding would improve reproducibility.","section":"References"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is the first genuinely sparse noncommutative Positivstellensatz, and the extraction machinery is a real step forward. But the proof of Theorem 3.3, which everything downstream leans on, has a hole at the p=2 amalgamation step. The hole looks fixable, but as printed the theorem is not proven.\n\nWhat's new: The paper proves a sparse version of Helton-McCullough under RIP (Assumption 2.4), gives a sparse GNS extraction theorem, and shows by counterexample that no sparse SOHS theorem exists and that low-order sparse bounds can be strictly below the true optimum. The convergence corollaries and the trace variant are useful. The numerical section demonstrates real speedups, and the examples (chained singular, Rosenbrock, random cubics on the nc polyball) are well chosen.\n\nWhere it wobbles: The gap in Theorem 3.3. In the p=2 proof, after constructing H(I1∩I2) and the operators A12_i, the authors apply the amalgamation theorem with common algebra B(H(I1∩I2)) and 'canonical embeddings' ι_k: B(H(I1∩I2)) → B(H(Ik)). These embeddings generally don't exist: the *-algebra generated by the A12_i may be much smaller than B(H12), and a homomorphism from full B(H12) is not determined by the images of these generators. The claim that B(H12) contains that algebra as a dense subset is only true when the representation is irreducible, which isn't guaranteed. The same issue recurs in the induction step and in Proposition 6.5. The likely repair, as you note, is to amalgamate the universal C*-algebra of the intersection variables (with state from L12) rather than full B(H12). If that works, the theorem survives; as written, it's a gap in the main theorem.\n\nOther soft spots: the general-p induction in Theorem 4.2 is sketched, and the numerical data has no code or seeds, so it's not auditable. Both are addressable in revision. The RIP condition is load-bearing—Example 3.4 shows exactly what goes wrong without it—but the authors are explicit about that, so it's a boundary, not a flaw.\n\nNet: the ideas are solid, the novelty is real, and the gap is likely repairable. This deserves a serious referee, but the referee should insist on a corrected proof of Theorem 3.3 and reproducible numerics before acceptance. I wouldn't cite the main theorem in its current state.","headline":"Real new sparse theory with a genuine but likely fixable gap in the main proof; worth refereeing, not citable as-is.","tokens_in":38019,"tokens_out":3679,"would_cite":false,"duration_ms":34954,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","47N10","13J10"],"pacs":[],"model":"deepseek-v4-flash","headline":"A sparse Positivstellensatz for noncommuting variables makes semidefinite hierarchies converge with cluster-sized matrices.","keywords":["noncommutative polynomial optimization","sparsity","semidefinite programming","Positivstellensatz","eigenvalue optimization","trace optimization","GNS construction","running intersection property"],"falsifier":"Compute the sparse hierarchy bounds for a strictly positive noncommutative polynomial on the noncommutative polydisc with chain clusters $I_k = \\{k, k+1\\}$ and compare them with the dense bounds or the true minimum; if any relaxation order shows a strict gap that never closes, then Theorem 3.3 or Corollary 5.9 fails. A search over random sparse polynomials with such clusters is a concrete test.","tokens_in":36933,"feed_emoji":"🧩","tokens_out":9434,"duration_ms":82693,"temperature":0.7,"pith_summary":"The paper proves a sparse version of the noncommutative Positivstellensatz: if a polynomial in noncommuting variables is strictly positive on an operator semialgebraic set, and the variables are grouped into overlapping clusters satisfying boundedness and the running intersection property, then the polynomial lies in the sparse quadratic module generated by the cluster polynomials. From this representation theorem the authors derive semidefinite programming hierarchies whose lower bounds converge to the true minimal eigenvalue and to the type-II1 minimal trace of a noncommutative polynomial. The practical upshot is that the semidefinite programs are indexed by words in each cluster, so their size grows with cluster sizes rather than with the full exponential count in the total number of variables. A sparse GNS construction is also provided, which extracts an optimizing matrix tuple and vector when flatness and irreducibility hold.","feed_headline":"Sparsity shrinks noncommutative polynomial SDPs to cluster size","feed_subtitle":"Under a running-intersection condition, cluster-sized semidefinite programs certify minimal eigenvalues and traces.","key_machinery":"The load-bearing mechanism is amalgamation of $C^*$-algebras with specified states, applied to the GNS representations of the cluster linear functionals. Each cluster functional $L_k$ gives a Hilbert space and a tuple of operators $\\hat A^k$ realizing $L_k$ on $\\mathbb{R}\\langle X(I_k)\\rangle$; the running intersection property — each new cluster meets the union of its predecessors inside one predecessor — guarantees that the overlaps of clusters correspond to common subalgebras, and the state-preserving amalgamation theorem glues these into one operator tuple $A$ on a Hilbert space, with a cyclic vector $w$ such that $L(f)=\\langle f(A)w,w\\rangle$. The sparse quadratic module $M(S)_{\\mathrm{sparse}} = M(S)_1 + \\cdots + M(S)_p$ is the algebraic object being characterized. The running intersection property (2.7) is what makes the amalgamated representation well-defined; Example 3.4 shows that without it the representation can fail.","core_discovery":"The central discovery is Theorem 3.3, a sparse analogue of the Helton-McCullough archimedean Positivstellensatz. Under Assumptions 2.3 and 2.4 — an archimedean bound on the tuple, a cluster decomposition of the objective and constraints, and the running intersection property — strict positivity of $f$ on $D_\\infty^S$ is equivalent to membership in the sparse quadratic module $M(S)_{\\mathrm{sparse}}$. This single result powers Corollaries 5.9 and 6.6, which state that the sparse eigenvalue and trace hierarchies converge to $\\lambda_{\\min}(f,S)$ and $\\operatorname{tr}_{\\min}(f,S)_{\\mathrm{II}_1}$ respectively, at relaxation orders whose semidefinite matrices are built from cluster words. The paper also shows the limits of the approach: there is no sparse analogue of the unconstrained sums-of-hermitian-squares theorem, and without the running intersection property positivity alone does not force sparse membership, as Example 3.4 demonstrates.","pith_inferences":["For clusters arising from chordal extensions of a correlation graph, the running intersection property should hold automatically, so the practical bottleneck is likely to be verifying it for user-supplied clusterings rather than the SDP size itself.","The same amalgamation proof strategy should extend to other positivity certificates, such as sparse convex Positivstellensätze and representations with noncommutative rational functions, giving design principles for future sparse hierarchies.","The strictness phenomenon in the unconstrained case suggests that users should check whether the objective is itself a sparse sum of hermitian squares before trusting the sparse bound; if not, merging clusters could improve the bound.","A randomized search for flat optimal solutions, already natural in dense noncommutative optimization, could make SparseGNS fully automatic; the paper indicates this route but does not implement it."],"forward_implications":["Sparse eigenvalue relaxations converge to $\\lambda_{\\min}(f,S)$, so a many-variable objective that decomposes into small clusters can be certified by solving much smaller SDPs.","Sparse trace relaxations converge to the type-II1 trace minimum, matching the dense theory's target rather than merely approximating finite-matrix traces.","When the optimal Hankel and localizing matrices satisfy flatness and irreducibility, the SparseGNS algorithm outputs an explicit tuple of symmetric matrices and a unit vector attaining the optimum.","The unconstrained sparse eigenvalue bound is always a valid lower bound but can be strictly below the true value, because sparse sums of hermitian squares do not exhaust sparse positive polynomials (Lemma 5.2)."],"supporting_citations":[{"why":"States the dense noncommutative Positivstellensatz (Theorem 2.2) that Theorem 3.3 sparsifies.","marker":"[HM04]"},{"why":"Introduces the commutative sparse Positivstellensatz and the running intersection hypotheses adapted here.","marker":"[Las06]"},{"why":"Provides the cluster-selection procedure via chordal extension and the same RIP condition in the commutative SOS hierarchy.","marker":"[WKKM06]"},{"why":"Supplies the amalgamation theorem for $C^*$-algebras with states used to glue cluster GNS representations.","marker":"[Bla78]"},{"why":"Baseline dense theory for noncommutative eigenvalue and trace optimization, flat extensions, and GNS extraction; most sparse results are stated as its sparse analogues.","marker":"[BKP16]"},{"why":"Establishes the sums-of-hermitian-squares theorem whose sparse analogue is shown to fail in Lemma 5.2.","marker":"[Hel02]"},{"why":"Provides the factorization and flatness technique underlying the finite-dimensional GNS and optimizer extraction.","marker":"[McC01]"},{"why":"Gives the dense noncommutative eigenvalue hierarchy that the sparse hierarchy refines.","marker":"[PNA10]"}],"fun_headline_variants":["Sparse noncommutative SDPs converge to exact bounds","Cluster-sized SDPs solve sparse noncommutative optimization","Sparse Positivstellensatz for noncommutative polynomials","Running intersection enables cluster-sized noncommutative SDPs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole convergence argument rests on Assumption 2.4(iii), the running intersection property relating the clusters; if that condition fails, positivity does not imply membership in the sparse module, as Example 3.4 shows with clusters {1,2}, {2,3}, {1,3}.","fun_headline_variants_meta":{"raw":{"variants":["Sparse noncommutative SDPs converge to exact bounds","Cluster-sized SDPs solve sparse noncommutative optimization","Sparse Positivstellensatz for noncommutative polynomials","Running intersection enables cluster-sized noncommutative SDPs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000815,"raw_usage":{"total_tokens":3556,"prompt_tokens":911,"completion_tokens":2645,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":527,"completion_tokens_details":{"reasoning_tokens":2572}},"tokens_in":527,"tokens_out":2645,"duration_ms":17692,"temperature":1.0,"reasoning_tokens":2572,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:45:48.773289+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the sparse hierarchy bounds for a strictly positive noncommutative polynomial on the noncommutative polydisc with chain clusters $I_k = \\{k, k+1\\}$ and compare them with the dense bounds or the true minimum; if any relaxation order shows a strict gap that never closes, then Theorem 3.3 or Corollary 5.9 fails. A search over random sparse polynomials with such clusters is a concrete test.","supporting_citations":[],"review_version":1}