{"id":"8a9ed171-2bda-4f1a-8111-2abac17fa71a","arxiv_id":"1908.05155","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"The SOS hierarchy on the sphere converges at rate O(d^2/l^2) for homogeneous polynomials of degree 2n with n≤d, quadratically improving Reznick's O(d/l).","lead":"This paper proves a faster convergence rate for the sum-of-squares hierarchy when maximizing polynomials on the unit sphere: the error now drops quadratically, not linearly, as the hierarchy level grows. The improvement extends to matrix-valued polynomials and produces new convergence bounds for the Best Separable State problem in quantum information.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 7's constant estimates are not established: both the DJ12 root bound and the h'(1)≤7n/3 bound fail for small d (e.g., d=2); the O(d²/ℓ²) rate likely survives with corrected constants.","rationale":"The paper's central claim is Theorem 2, with Theorem 1 as a corollary, and the proof reduces the rate statement to Proposition 7 via the quantity ρ2n(d, ℓ). I checked the two numerical inequalities used in Proposition 7 directly. The h'(1) bound is false under n ≤ d: substituting n = d = 2 into the paper's exact formula gives h'(1) = 10, while 7n/3 ≈ 4.67. The root bound is also not valid for the Gegenbauer family used in the paper when d is small: for d = 2 the orthogonal polynomials are Chebyshev polynomials, and the largest zero of T_{ℓ+1} is cos(π/(2(ℓ+1))), whose gap π²/(8ℓ²) exceeds the claimed d²/(4ℓ²) = 1/ℓ² for ℓ = 10 and asymptotically. Therefore the proof of Proposition 7, and hence the explicit constants in Theorems 1 and 2, are not established as written. I do not treat this as a refutation of the main rate claim: Theorem 2 only asserts existence of constants Cn and C'n, and a corrected root bound with a slightly larger universal constant, together with a valid bound like h'(1) ≤ 5n for n ≤ d, would still give ρ2n(d, ℓ) = O_n(d²/ℓ²) for ℓ ≥ C n d. Thus the central mathematical content is plausible and likely correct, but the written proof needs a repair. The quantum duality theorem (Theorem 12) appears to be a separate contribution and is not affected by this gap. The reader's weakest_assumption identifies the same two failing inequalities; I agree that the appropriate verdict is conditional rather than rejection or acceptance.","tokens_in":23673,"tokens_out":24197,"duration_ms":242352,"concrete_test":"Take d = 2, n = 2, ℓ = 10, so C_k = T_k and h = (T_2 + T_4)/2. Using orthonormal Chebyshev polynomials p_i, form the (ℓ+1)×(ℓ+1) matrix T[h]_{ij} = ∫_{-1}^1 p_i(t)p_j(t)h(t)(1−t²)^{−1/2}dt and compute its largest eigenvalue numerically with Gauss–Chebyshev quadrature. Compare it with the Proposition 7 lower bound 1 − (7n/12)(d/ℓ)² = 1 − 14/1200 ≈ 0.98833. Separately verify the two intermediate claims: cos(π/22) ≈ 0.98982 < 1 − 1/100 = 0.99, and h'(1) = 10 > 14/3. If the computed λmax is below 0.98833, Proposition 7 is false as stated; if it is above, the cited proof steps are still invalid and must be replaced before the stated constants can be accepted.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In Section 3, Proposition 7 claims λmax(T[h]) ≥ 1 − (7n/12)d²/ℓ² for h = (1/n)∑_{k=1}^n C_{2k}/C_{2k}(1) and n ≤ d. The proof rests on two inequalities. First, it cites [DJ12, Section 2.3] for the bound x_{ℓ+1,ℓ+1} ≥ 1 − d²/(4ℓ²) on the largest zero of C_{ℓ+1}. For d = 2 the polynomials C_k are the Chebyshev polynomials T_k, and the largest zero of T_{ℓ+1} is cos(π/(2(ℓ+1))) ≈ 1 − π²/(8ℓ²). This is strictly smaller than 1 − 1/ℓ² = 1 − d²/(4ℓ²) for ℓ = 10 and asymptotically for all larger ℓ, so the stated root bound fails exactly in the regime used. Second, the proof asserts h'(1) ≤ 7n/3 from the displayed formula h'(1) = (n+1)(3d+4n−4)/(3(d−1)) and n ≤ d. At n = d = 2 this gives h'(1) = 10, while 7n/3 = 14/3; the inequality is false. Consequently the stated lower bound on λmax(T[h]) and therefore the constants in Theorem 2 and Theorem 1 are not proven. This is a correctness gap in the written proof, although it concerns constants and thresholds rather than the quadratic-in-(d/ℓ) rate: a corrected root bound with a slightly larger constant and a uniform bound like h'(1) ≤ 5n for n ≤ d would preserve the O(d²/ℓ²) conclusion.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the convergence rate of the Lasserre/sum-of-squares hierarchy for maximizing a homogeneous polynomial of degree 2n on the unit sphere S^{d-1}. Its main result, Theorem 2, states that for n ≤ d and a homogeneous matrix-valued polynomial F of degree 2n with 0 ≤ F ≤ I on the sphere, F + C'_n (d/ℓ)^2 I is ℓ-sos whenever ℓ ≥ C_n d, with constants depending only on n; Theorem 1 is the scalar corollary asserting (p_ℓ − p_min)/(p_max − p_min) ≤ 1 + (C_n d/ℓ)^2. The proof uses positive kernels K(x,y) = q(⟨x,y⟩)^2 and analyzes their Gegenbauer coefficients through generalized Toeplitz matrices. The paper also proves a duality theorem (Theorem 12) identifying the dual of the DPS hierarchy in quantum information with real sum-of-squares certificates of the associated Hermitian polynomial, and uses it to transfer the rate result to the Best Separable State problem, recovering and generalizing the quadratic convergence rate of Navascués, Owari and Plenio. A tightness result (Theorem 10) shows the quadratic rate cannot be improved in the quadratic case.","tokens_in":23997,"tokens_out":17674,"duration_ms":170830,"significance":"If the proof is repaired, the paper settles an open question raised by de Klerk and Laurent by improving the known O(d/ℓ) rate for the upper-bound SOS hierarchy on the sphere to O(d^2/ℓ^2). The matrix-valued formulation with constants independent of the matrix size is a real strength, as is the self-contained proof of the DPS/SOS duality, which fills a gap in the literature. The recovery of the known NOP09 rate provides a useful external check, and the tightness analysis for quadratic polynomials is a good addition. However, the proof of the general-degree rate rests on Proposition 7, and two inequalities used there are false as stated. Because Proposition 7 is the only step producing the O(d^2/ℓ^2) estimate on ρ_{2n}, the constants in Theorems 6, 2, and 1 are not established in the present manuscript. The errors concern constants and thresholds rather than the overall proof architecture, so the central claim remains plausible and likely repairable.","major_comments":[{"comment":"The proof invokes the bound x_{ℓ+1,ℓ+1} ≥ 1 − d^2/(4ℓ^2) from [DJ12, Section 2.3]. This bound is false for d = 2, which is in the admissible range n ≤ d. For d = 2 the Gegenbauer polynomials are (up to scaling) the Chebyshev polynomials, so the largest zero of C_{ℓ+1} is cos(π/(2(ℓ+1))) = 1 − π^2/(8ℓ^2) + O(ℓ^{-3}), which is strictly smaller than 1 − 1/ℓ^2 for ℓ = 10 and asymptotically for all larger ℓ. The authors need either a valid universal root bound with a larger constant, or an explicit dimension restriction together with a separate argument for the excluded small dimensions.","section":"Section 3, Proposition 7"},{"comment":"The assertion h'(1) ≤ 7n/3, derived from h'(1) = (n+1)(3d+4n−4)/(3(d−1)) and n ≤ d, is false. For n = d = 2 one has h'(1) = 10, while 7n/3 = 14/3. In fact, for d = n the exact value is h'(1) = 7n/3 + (10n−4)/(3(n−1)), which exceeds 7n/3 for every n ≥ 2. Consequently the final lower bound λ_max(T[h]) ≥ 1 − (7n/12)d^2/ℓ^2 is not proven. A correct uniform bound such as h'(1) ≤ 5n for n ≤ d would repair the argument with a different constant.","section":"Section 3, Proposition 7"},{"comment":"Because Proposition 7 is the only step that bounds ρ̃_{2n}(d,ℓ) by O(d^2/ℓ^2), and because Proposition 9 transfers that bound to ρ_{2n}(d,ℓ), the false inequalities in Proposition 7 leave the constants C_n and C'_n in Theorems 6, 2, and 1 unproven as written. The O(d^2/ℓ^2) rate may well survive with corrected constants, but the current proof is incomplete at this load-bearing point.","section":"Section 3, Theorems 6, 2, and 1"}],"minor_comments":[{"comment":"The phrase “where C, C′ > 0 is some absolute constant” should be “where C, C′ > 0 are absolute constants.”","section":"Section 4.4, Theorem 15"},{"comment":"The inverse λ_{2k}^{-1} in the definition of ρ_{2n}(d,ℓ) presupposes λ_{2k} ≠ 0; the authors could state explicitly that the minimization can be restricted to polynomials for which the even Gegenbauer coefficients are positive, since otherwise the objective is not well defined.","section":"Section 3, Eq. (13)"},{"comment":"The notation in Eq. (22) uses a bracehtipup/down artefact in the displayed formula; this should be cleaned up to a standard partial-transpose notation such as (I_A ⊗ T_{B_1} ⊗ ⋯ ⊗ T_{B_s} ⊗ I_{B_{s+1}} ⊗ ⋯ ⊗ I_{B_ℓ}).","section":"Section 4.1, Eq. (22)"}],"recommendation":"major_revision","confidential_remarks":"The paper is original and the duality theorem is a genuine contribution. My main concern is confined to Proposition 7, but it is load-bearing for the headline rate. The errors appear fixable with corrected constants, so I recommend major revision rather than rejection. No concerns about citation practices or novelty disclosure."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this is a worthwhile paper that deserves a serious referee, but the proof of the main rate has two numerical inequalities that are simply false as written. The strategy and the theorem are probably right; the constants are not established.\n\nWhat is new: the kernel optimization idea — tuning a univariate q(t) through a generalized Toeplitz eigenvalue problem to make the Gegenbauer coefficients converge quadratically — is a real improvement over Reznick's d/ℓ kernels. The matrix-valued version is a nice extension, and the formal proof of the DPS/SOS duality (Theorem 12) fills a gap that had been circling the literature. Recovering NOP09 from a SOS argument is a neat byproduct. No fitted parameters, no self-citation games; the NOP09 recovery is an independent sanity check.\n\nWhere it wobbles: Proposition 7's closing inequality chain. First, the cited DJ12 bound x_{ℓ+1,ℓ+1} ≥ 1 − d²/(4ℓ²) fails for d=2, where the largest zero is cos(π/(2(ℓ+1))) ≈ 1 − π²/(8ℓ²), smaller than 1 − 1/ℓ². Second, the claim h'(1) ≤ 7n/3 is false: at n=d=2, h'(1)=10 while 7n/3=14/3, and in fact h'(1) > 7n/3 whenever n=d. Both failures are in the last two displayed steps of Proposition 7. These are constant-scale errors, not structural ones: a correct root bound with a slightly larger constant and a uniform bound h'(1) ≤ c n would preserve the O(d²/ℓ²) conclusion. But as written the proof does not establish the constants in Theorems 1 and 2.\n\nThe rest of the paper is solid. The duality proof in Appendix B is careful, and the attention to monomial sets in the rsos vs csos distinction is right. The tightness argument for n=2 also looks fine.\n\nWho this is for: anyone working on SOS convergence rates, Lasserre hierarchies, or DPS hierarchies in quantum information. The paper deserves a rigorous referee—send it out. The authors should fix Proposition 7 before publication.\n\nBest,","headline":"A valuable paper with a genuinely new quadratic rate and a clean DPS/SOS duality, but Section 3 contains two false constant bounds that must be fixed before it is citable as is.","tokens_in":24544,"tokens_out":4469,"would_cite":true,"duration_ms":40543,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C22","90C26","33C45","14P10"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that the sum-of-squares hierarchy on the sphere converges at rate O(d^2/ℓ^2) and transfers that rate to quantum entanglement bounds.","keywords":["sum-of-squares hierarchy","polynomial optimization on the sphere","Gegenbauer polynomials","convergence rate","matrix-valued polynomials","DPS hierarchy","best separable state","quantum entanglement"],"falsifier":"Compute the largest zero of $C_{\\ell+1}$ for $d=2$, $\\ell=10$: it is about $0.9898$, below the lower bound $1 - d^2/(4\\ell^2) = 0.99$, so checking the quoted zero bound over the paper's full parameter range would settle whether the proof's constants hold. One can also evaluate $h'(1) = (n+1)(3d+4n-4)/(3(d-1))$ at $n=d$ and compare it with $7n/3$.","tokens_in":23449,"feed_emoji":"🎯","tokens_out":13888,"duration_ms":124618,"temperature":0.7,"pith_summary":"This paper establishes that the sum-of-squares (SOS) hierarchy for maximizing a homogeneous polynomial of degree $2n$ on the unit sphere $\\mathbb{S}^{d-1}$ converges at the rate $O(d^2/\\ell^2)$ once the level $\\ell$ is at least a constant times $d$, where the constants depend only on $n$. This improves the previously known $O(d/\\ell)$ rate by a quadratic factor and answers an open question from recent work on SOS upper bounds on the sphere. The same statement holds for matrix-valued polynomials on the sphere, with bounds independent of the matrix size. Via a duality between sums of squares and the DPS hierarchy of separable quantum states, the result yields an $O(d_B^2/\\ell^2)$ convergence rate for the Best Separable State problem and extends to polynomials of arbitrary even degree. The proof rests on constructing a polynomial kernel whose Gegenbauer coefficients approach $1$ at the faster rate.","feed_headline":"Sphere SOS hierarchy converges at rate (d/ℓ)²","feed_subtitle":"A polynomial-kernel trick sharpens sphere-optimization certificates and quantum separability bounds.","key_machinery":"The engine is the polynomial kernel $K(x,y) = q(\\langle x,y\\rangle)^2$ on $\\mathbb{S}^{d-1} \\times \\mathbb{S}^{d-1}$. The Funk-Hecke formula diagonalizes this integral operator: its eigenvalues are the Gegenbauer coefficients $\\lambda_{2k}$ of the univariate polynomial $\\varphi(t)=q(t)^2$, and if those coefficients are close enough to $1$, then $K^{-1}(F+\\delta I)$ is nonnegative and $F+\\delta I = K K^{-1}(F+\\delta I)$ is an explicit sum of squares. Choosing $q$ is recast as a generalized Toeplitz eigenvalue problem: $\\rho_{2n}(d,\\ell) = \\min_{\\|e\\|=1} \\sum_{k=1}^n |(e^T T[C_{2k}/C_{2k}(1)]e)^{-1}-1|$, with $T[h]$ the truncated multiplication matrices for normalized Gegenbauer polynomials. The asymptotic rate comes from lower-bounding the largest eigenvalue of $T[h]$ for $h = \\frac{1}{n}\\sum_{k=1}^n C_{2k}/C_{2k}(1)$ via the largest root of $C_{\\ell+1}$, and the matrix-valued case follows by applying the same harmonic-component bounds entrywise with spectral norms.","core_discovery":"The central claim is Theorem 2: if $F(x)$ is a homogeneous symmetric matrix-valued polynomial of degree $2n$ in $d$ variables with $n \\le d$ and $0 \\le F(x) \\le I$ on $\\mathbb{S}^{d-1}$, then for every $\\ell \\ge C_n d$ the polynomial $F + C'_n (d/\\ell)^2 I$ is a sum of squares of polynomials of degree at most $\\ell$ on the sphere. For the scalar polynomial $F = (p_{\\max}-p)/(p_{\\max}-p_{\\min})$, this gives $(p_\\ell-p_{\\min})/(p_{\\max}-p_{\\min}) \\le 1 + (C_n d/\\ell)^2$, a quadratic improvement over the previously known rate. The more general Theorem 6 bounds every level $\\ell$ through a quantity $\\rho_{2n}(d,\\ell)$ that can be computed for degree $2$ and $4$, and the $O(d^2/\\ell^2)$ rate is shown tight for quadratic polynomials. A duality theorem identifies the DPS hierarchy of separable quantum states with a real-sum-of-squares condition on Hermitian polynomials, so the same rate transfers to the Best Separable State problem: $h_{\\mathrm{Sep}}(M) \\le h_{\\mathrm{DPS}_\\ell}(M) \\le (1 + C d_B^2/\\ell^2) h_{\\mathrm{Sep}}(M)$ for $\\ell \\ge C' d_B$.","pith_inferences":["A direct numerical computation of $\\rho_{2n}(d,\\ell)$ for small $d$ would test whether the $O(d^2/\\ell^2)$ scaling persists outside the proven regime $\\ell \\ge C_n d$.","The same kernel construction transfers naturally to products of spheres, since a matrix-valued polynomial in $x$ is a bihomogeneous polynomial in $(x,y)$; this would give SOS-based bounds for multilinear optimization.","If the quadratic-case tightness is representative, the $d^2/\\ell^2$ rate is likely the true order of the SOS upper-bound hierarchy on the sphere, and further speedups would require a different relaxation family rather than a sharper kernel."],"forward_implications":["For a homogeneous polynomial of fixed degree $2n$, reaching relative accuracy $\\varepsilon$ requires level $\\ell = O(d/\\sqrt{\\varepsilon})$ rather than $O(d/\\varepsilon)$.","The certificate level is independent of the size of the matrix-valued polynomial, so operator-valued or multi-constraint problems do not require deeper levels.","The DPS hierarchy approximates the best separable state value with relative error $O(d_B^2/\\ell^2)$ at level $\\ell \\ge C d_B$, with constants independent of the other subsystem dimension.","The duality theorem makes the quantum convergence rate a special case of the SOS rate, so the same bound applies to nonquadratic Hermitian polynomials."],"supporting_citations":[{"why":"supplies the bound on the largest zero of Gegenbauer polynomials that converts the Toeplitz eigenvalue estimate into the $d^2/\\ell^2$ rate.","marker":"[DJ12]"},{"why":"provides the previous sphere SOS rate and the Laplacian bound used to control harmonic components.","marker":"[Rez95]"},{"why":"establishes the prior $d/\\ell$ convergence rate for SOS on the hypersphere that Theorem 1 improves.","marker":"[DW12]"},{"why":"posed the $O(1/\\ell^2)$ question for the SOS upper-bound hierarchy that Theorem 1 answers.","marker":"[dKL19]"},{"why":"proved the $d_B^2/\\ell^2$ convergence rate for the DPS hierarchy via quantum arguments, recovered here as a special case.","marker":"[NOP09]"},{"why":"defines the DPS hierarchy of extendible quantum states whose convergence Theorem 4 bounds.","marker":"[DPS04]"},{"why":"gives the eigenvalue-root relation for generalized Toeplitz matrices used in Proposition 8.","marker":"[Par65]"},{"why":"supplies the Toeplitz multiplication property used in the tightness proof for quadratic polynomials.","marker":"[Bax71]"},{"why":"gives the complementary upper bound on the largest Gegenbauer zero used to show the quadratic rate is tight.","marker":"[ADGR04]"}],"fun_headline_variants":["Quadratic speedup for sphere SOS hierarchy","Sphere SOS convergence rate improved to O(d²/ℓ²)","Solving open problem: sphere SOS rate O(d²/ℓ²)","Tighter sphere SOS bounds for quantum separability","Polynomial kernel sharpens sphere SOS and separability"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof's explicit constants in the $O(d^2/\\ell^2)$ estimate rest on two literature bounds holding throughout the asserted range: the largest zero of the Gegenbauer polynomial $C_{\\ell+1}$ is at least $1 - d^2/(4\\ell^2)$, and the derivative $h'(1)$ of $h = \\frac{1}{n}\\sum_{k=1}^n C_{2k}/C_{2k}(1)$ is at most $7n/3$; if either fails, those constants are not established.","fun_headline_variants_meta":{"raw":{"variants":["Quadratic speedup for sphere SOS hierarchy","Sphere SOS convergence rate improved to O(d²/ℓ²)","Solving open problem: sphere SOS rate O(d²/ℓ²)","Tighter sphere SOS bounds for quantum separability","Polynomial kernel sharpens sphere SOS and separability"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000213,"raw_usage":{"total_tokens":1468,"prompt_tokens":1038,"completion_tokens":430,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":654,"completion_tokens_details":{"reasoning_tokens":352}},"tokens_in":654,"tokens_out":430,"duration_ms":4521,"temperature":1.0,"reasoning_tokens":352,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:24:57.536854+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Compute the largest zero of $C_{\\ell+1}$ for $d=2$, $\\ell=10$: it is about $0.9898$, below the lower bound $1 - d^2/(4\\ell^2) = 0.99$, so checking the quoted zero bound over the paper's full parameter range would settle whether the proof's constants hold. One can also evaluate $h'(1) = (n+1)(3d+4n-4)/(3(d-1))$ at $n=d$ and compare it with $7n/3$.","supporting_citations":[],"review_version":1}