{"id":"4078cd79-5716-4f87-bd7f-c84bf75715ed","arxiv_id":"2608.10184","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Random ellipsoid fitting in R^d has a sharp satisfiability transition at n ~ d^2/4 Gaussian points: it is feasible below and infeasible above.","lead":"This paper proves a 2013 conjecture about when random points in high-dimensional space can all lie exactly on the surface of some centered ellipsoid. The answer is a sharp threshold at n around d^2/4 points: below it a fit almost surely exists, and above it almost surely does not.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Unsatisfiable-phase no-fit rests on Proposition 4.3, proved via Proposition 4.8, a sketched extension of Bandeira–Maillard free-entropy universality to arbitrary row offsets and Schatten-3-constrained priors.","rationale":"I read the intended claim: exact resolution of the Saunderson–Parrilo–Willsky conjecture with a sharp threshold at n/d²=1/4. The satisfiable side is carried by explicit, internally coherent arguments: the head-tail decomposition, the uniform head-section width via the inverse feature Gram matrix, the second-chaos Lindeberg principle, and the clipped soft min-max concentration all have detailed proofs supported by stated external results. The unsatisfiable side is more delicate: no-fit is proved by conditioning on a low-rank spectral head and Gaussianizing only the diffuse bulk, and the bridge from the Gaussian surrogate bulk back to the quadratic bulk is Proposition 4.3. That proposition rests on Proposition 4.8, which is not actually proved in the manuscript but asserted as a straightforward rowwise extension of an external free-entropy universality theorem, with the crucial uniformity over arbitrary deterministic offsets and Schatten-3-constrained finite priors left to the reader. This is precisely the junction where the no-fit conclusion for n/d²>1/4 could fail: if the BM25 proof of common-loss universality needs centering, bounded offsets, or a row-independent prior, then the conditional comparison (143) in Lemma 4.12 has no basis, and the transfer of the hybrid risk gap to the ellipsoid model collapses. I found no independent verification, no formal check, and no detailed derivation of this extension. I agree with the reader's identification of this as the weakest load-bearing assumption. A full proof of Proposition 4.8, or a precise reduction to [BM25, Theorem 4.6] with all uniformity checks explicit, would settle the concern. Until then, the conditional verdict is appropriate, and my stress-test does not change it.","tokens_in":41844,"tokens_out":19118,"duration_ms":196964,"concrete_test":"Independently write out the complete proof of Proposition 4.8 following [BM25, Theorem 4.6] with row losses ℓ_i(u)=βφ(a_i+u). Verify that the domination estimate, the Schatten-3 pointwise-normality lemma, and the bounded-test-function smoothing are uniform over (a_i)∈R^n, over 1≤n≤Λm², and over all finite A⊂T_m(C0,κ); in particular check that no step uses E a_i=0, bounded a_i, equality of the offsets across rows, or a common loss. If every estimate is uniform, Proposition 4.3 is supported. If the proof needs an extra condition, identify it and determine whether the head-dependent offsets satisfy it; if not, Theorem 1.2(b) is not established. A finite-size numerical comparison of the two sides of (103) would be a sanity check but cannot settle the asymptotic uniform statement.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The unsatisfiable phase of Theorem 1.2 is only as secure as Proposition 4.3, the bulk universality transfer. Proposition 4.5 and the final contradiction in Theorem 4.1 inherit the hybrid-model risk gap from that comparison, and Proposition 4.3 is proved through Proposition 4.8. Section 4.2 does not give a proof of Proposition 4.8: it asserts that [BM25, Theorem 4.6], stated for a common row loss, extends rowwise to losses ℓ_i(u)=βφ(a_i+u) with arbitrary deterministic offsets, finite priors A_m⊂T_m, and uniformity over n≤Λm², offsets, and priors. The load-bearing content is exactly that uniformity. In the application, a_i=g_i^T H g_i−TrH−b depends on the head variables; these offsets are neither centered nor bounded a priori, and Lemma 4.12 needs the comparison conditionally on every head realization in E_U. If the BM25 proof uses the common-loss assumption—through centering, through boundedness of the loss argument, or through a prior that is independent of the row—then (143) has no support and the transfer of the hybrid risk gap to the ellipsoid model fails. The paper says the proof is rowwise and that only differences are sketched; that is plausible but unverified. This is not a known counterexample, but a missing-support concern at the exact junction where the no-fit conclusion for n/d²>1/4 is established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proves the Saunderson–Parrilo–Willsky ellipsoid fitting conjecture: for n independent standard Gaussian vectors in R^d, exact feasibility of S ⪰ 0 with x_i^T S x_i = d for all i exhibits a sharp phase transition at n ~ d^2/4. Theorem 1.2 gives existence with probability tending to one when lim sup n/d^2 < 1/4, and nonexistence when lim inf n/d^2 > 1/4, with no spectral restriction on the fitted matrix. Theorem 1.3 strengthens the satisfiable phase to a well-conditioned fit, and Corollary 1.4 gives the equivalent threshold for balanced positive definite combinations. The satisfiable side is proved by a dual separation argument with an explicit head–tail decomposition of the dual vector, exact head correction, a second-order chaos Lindeberg principle, and a careful net argument. The unsatisfiable side splits a candidate matrix into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianizes the bulk conditionally on the head, proves a uniform positive risk gap in a hybrid model via Gordon's escape theorem, and transfers the gap back to the original model via a translated-loss bulk universality proposition.","tokens_in":42157,"tokens_out":11886,"duration_ms":113435,"significance":"If correct, this is a major result: it resolves a long-standing conjecture with a sharp, parameter-free threshold that emerges from the statistical dimension d(d+1)/4 of the PSD cone (Lemma 2.1), and it closes the two gaps left by Bandeira and Maillard — exact fitting and the removal of the operator-norm constraint. The satisfiable side is carefully developed, with explicit lemmas, quantitative condition-number bounds, and a self-contained Gaussian comparison principle. The unsatisfiable side has a clear and credible architecture, but its central transferred-loss universality result, Proposition 4.8, is only sketched as a rowwise modification of an external theorem. Because that proposition is load-bearing for the no-fit phase, the paper is not fully supported as written.","major_comments":[{"comment":"The proof of Proposition 4.8 is not supplied. The paper states that [BM25, Theorem 4.6], asserted for a common row loss, extends rowwise to losses ℓ_i(u)=βφ(a_i+u) with arbitrary deterministic offsets, finite priors A_m⊂T_m, and uniformity over n≤Λm², and that only the differences are sketched. This is load-bearing: Proposition 4.3 uses that uniformity to compare the ellipsoid bulk with the Gaussian bulk for every deterministic offset, and Lemma 4.12 then applies it conditionally on every head realization in E_U, Eq. (143). In the application the offsets a_i = g_i^T H g_i − TrH − b are neither centered nor bounded a priori, so any use of centering, boundedness of the loss argument, or a row-independent prior in [BM25, Theorem 4.6] would invalidate (143). If this extension fails, the no-fit conclusion for lim inf n/d^2 > 1/4 does not follow. Please provide a complete proof of Proposition 4.8, or a precise verification that all hypotheses of [BM25, Theorem 4.6] hold rowwise and uniformly over the offsets and priors used in Section 4.","section":"§4.2, Prop. 4.8 (used in Prop. 4.3, Prop. 4.5, Thm. 4.1)"},{"comment":"Proposition 4.3 is stated as a supremum over arbitrary deterministic offsets and closed subsets of B_m(C0,κ), and this uniformity is essential for the net transfer in Section 4.4. The proof via Lemma 4.9 relies on the feature-edge events (27) and Proposition 2.8, but the text does not explicitly verify that the required uniformity over n/m² ∈ [ε,1/2−ε] and over the offset-dependent subsets C_U(H) is preserved when Lemma 4.12 conditions on every head realization in E_U. Please state and justify the uniformity claim for (103) at the level of detail used elsewhere in the paper, so that the conditional o(1) in Lemma 4.12, Eq. (143), is unambiguous.","section":"§4.1 and §4.2, Prop. 4.3"}],"minor_comments":[{"comment":"The norm ∥G∥_{F→2} is used without definition; please define it as the operator norm from (S^p, ∥·∥_F) to (R^n, ∥·∥_2).","section":"§2.3, Prop. 2.8"},{"comment":"The reference [Sau11] lists the author as 'James James Francis Saunderson'; the duplicated first name appears to be a typo. The citation '[R V13]' should be '[RV13]'.","section":"References"},{"comment":"The sentence 'Lemma 2.4 also follows from the argument used for Lemma 2.3' is vague and unproved; since Lemma 2.4 is a standard Gordon escape estimate, either give a precise citation with the stated form or delete the sentence.","section":"§2.2, Lemma 2.4"},{"comment":"The notation O_τ(d^{3/2}) is introduced without explicit definition; state that the implied constant depends only on τ, and similarly for other subscripted constants in the net-entropy estimates.","section":"§4.1, Eq. (107)"},{"comment":"The statement of the second-chaos interpolation lemma uses the quantity R_{N,d} = E max_i ∥x_i∥_2^2; it would be helpful to note explicitly that this quantity is finite and uniform in the conditioning used later in Proposition 3.4, since the tail rows are not conditioned.","section":"§3.4, Lemma 3.9"},{"comment":"The disclosure of AI use is transparent and does not affect the mathematical assessment.","section":"Acknowledgments"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is clearly within scope and the satisfiable-side proof appears solid. The decisive issue is the unsatisfiable side: Proposition 4.8 is asserted as an extension of an external theorem with only a sketch, and the paper itself states that the proof is only sketched. Since the no-fit conclusion for n/d^2>1/4 passes through this proposition, I cannot recommend acceptance until a complete proof or a precise hypothesis check is supplied. There is no circularity: the threshold constant comes from Lemma 2.1 and the comparisons are against external results. The AI-use statement is honest and does not raise concerns."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — this is the real thing: a proof of the Saunderson–Parrilo–Willsky conjecture, exact fit and no operator-norm restriction. The satisfiable side is worked out in serious detail: head–tail decomposition of the dual vector, exact head correction through the inverse feature Gram matrix, a second-order chaos Lindeberg principle, and a careful net argument. The construction even gives well-conditioned fits below the threshold, which is a bonus. The unsatisfiable side has the right architecture — spectral head, Schatten-3 diffuse bulk, conditional Gaussianization, Gordon escape — and the hybrid risk gap is plausible.\n\nThe soft spot is exactly where the reader puts it. Proposition 4.8, the free-entropy comparison with arbitrary deterministic row offsets, is load-bearing for Propositions 4.3 and 4.5, and its proof is explicitly only sketched as a rowwise modification of [BM25, Theorem 4.6]. The paper itself says \"we only sketch the differences.\" That is not a manufactured flaw; it is the one place where the no-fit conclusion for n/d^2 > 1/4 is anchored to an external theorem whose common-loss assumption may be doing real work. The offsets a_i = g_i^T H g_i − Tr H − b are random, head-dependent, and not a priori bounded, and Lemma 4.12 needs uniformity over every head realization in E_U. If the BM25 proof uses centering or boundedness of the loss argument in a way that does not survive per-row deterministic translations, then (143) has no support. I have no counterexample, and the extension may be routine, but 'may be routine' is not a proof. The authors should either give the full argument or a precise reduction with the uniformity quantified.\n\nA secondary note: the acknowledgment says GPT 5.6 helped repair and complete several arguments. That is not a problem in itself, but it raises the bar for the sketched portion; I would want the referee to insist on the full derivation there.\n\nThis is a major result with a genuine, localized gap. It deserves a serious referee, not a desk rejection. My recommendation: send it out, ask for a complete proof of Proposition 4.8 (or a precise statement with all uniformity conditions checked), and keep the satisfiable side as the model of what the final version should look like. I would cite it and bring it to the reading group; the constant 1/4 computation alone is worth the time.","headline":"The paper proves the sharp SPW ellipsoid-fitting threshold at n ~ d^2/4, closing both gaps in Bandeira–Maillard; the only real weakness is that the unsatisfiable phase leans on a sketched universality extension (Prop 4.8) that deserves a full proof.","tokens_in":747,"tokens_out":871,"would_cite":true,"duration_ms":22131,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B20","60D05","90C22","52A22"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves that $n$ independent standard Gaussian points in $\\mathbb{R}^d$ admit an exact centered ellipsoid fit with high probability exactly when $n/d^2<1/4$, and almost never when $n/d^2>1/4$.","keywords":["ellipsoid fitting","phase transition","random semidefinite program","Gaussian equivalence","statistical dimension","conic integral geometry","random matrices","universality"],"falsifier":"Run the free-entropy comparison of Proposition 4.8 in the smallest non-degenerate case, say $n=1$, $m=2$, with a nonzero offset $a_1$ and the full Schatten-constrained set $C_m$; the proposition predicts the difference between the quadratic-chaos and GOE ground states vanishes as $m\\to\\infty$. A non-vanishing difference for any such offset would refute the bulk-universality step and with it the upper-bound theorem.","tokens_in":41637,"feed_emoji":"🎯","tokens_out":11483,"duration_ms":98218,"temperature":0.7,"pith_summary":"This paper settles a decade-old conjecture about when $n$ independent standard Gaussian points in $\\mathbb{R}^d$ all lie on the boundary of a common centered ellipsoid. The answer is sharp: if the density $n/d^2$ stays below $1/4$, a fitting positive-semidefinite matrix $S$ exists with probability tending to one, and can be chosen well-conditioned with all eigenvalues in a fixed interval; if $n/d^2$ stays above $1/4$, with probability tending to one no fit exists, even allowing wildly elongated ellipsoids. The threshold is the statistical dimension $d(d+1)/4$ of the positive semidefinite cone, and the proof transfers a Gaussian-surrogate phase transition to the exact, spectrally unrestricted problem.","feed_headline":"Below d^2/4, random points always fit an ellipsoid","feed_subtitle":"Above that many points, almost surely no centered ellipsoid passes through them all.","key_machinery":"The argument runs through a Gaussian-comparison transfer from a surrogate problem with GOE measurements to the actual rank-one quadratic measurements. On the satisfiable side, the key object is a head–tail decomposition of the dual vector: coordinates with large magnitude are collected into a sparse head whose constraints are solved exactly using the quadratic feature Gram matrix, whose two-sided singular values are of order $d$ throughout $n/d^2<1/2$; the remaining low-influence tail is compared to its Gaussian counterpart through a second-order Lindeberg principle. On the unsatisfiable side, any candidate $S$ is split into a low-rank spectral head $H$ (eigenvalues above $d^{-1/4}$) and a Schatten-3 diffuse bulk $B$; conditioning on the head and replacing the bulk quadratic form by $\\sqrt{m}$ times a GOE inner product produces a hybrid model, and an escape-through-a-mesh inequality yields a uniform positive risk gap for the hybrid model, which is then transferred back exactly. The constant $1/4$ enters only where the Gaussian width $d/2$ of the scaled positive semidefinite cap crosses $\\sqrt{n}$.","core_discovery":"The central discovery is that the exact feasibility problem for random quadratic constraints has the same threshold as its Gaussian surrogate: no spectral bound on the candidate matrix $S$ is needed, and no error tolerance is needed. Theorem 1.2 states that if $\\limsup n/d^2 < 1/4$ then with probability tending to one there exists $S \\succeq 0$ with $x_i^\\top S x_i = d$ for all $i$, and if $\\liminf n/d^2 > 1/4$ then with probability tending to one no such $S$ exists. In the satisfiable regime the proof yields more: for every fixed $\\alpha<1/4$, one can take $S$ with $\\lambda_- I \\preceq S \\preceq \\lambda_+ I$ for constants depending only on $\\alpha$ and with $\\mathrm{Tr}\\,S = d$, so the fitted ellipsoid's axes stay within constant factors of the sphere. In the unsatisfiable regime, the obstruction is uniform: an exponentially decaying loss gap holds over all trace-one PSD matrices without any operator-norm restriction. The same theorem, through the conic duality formulated in the paper, gives the sharp threshold for the alternative statement about the nonexistence or existence of balanced positive definite combinations of the random rank-one matrices.","pith_inferences":["The proof technique should transfer to other exact feasibility questions with rank-one or quadratic measurements, such as phase retrieval or matrix sensing, where Gaussian-surrogate thresholds are known but exact feasibility with no spectral restrictions has been open; the head-tail and head-bulk conditional Gaussianization is a plausible general repair mechanism.","The existence result below threshold does not settle the typical-solution structure predicted by replica theory, such as half the semiaxes diverging at criticality; the proof guarantees an atypical well-conditioned fit, so the typical geometry at the boundary remains open.","The sharpness at exactly $n=d^2/4$—the width of the crossover window and the finite-$d$ corrections—is not addressed; a natural conjecture from the statistical-dimension calculation is that the crossover has width of order $d^{3/2}$ or $d\\log d$, and the proof's estimates could likely be sharpened to locate it.","The asserted rowwise extension of free-entropy universality to translated losses (used for the unsatisfiable phase) can be tested on small systems, and a nonvanishing discrepancy there would de-risk the entire upper-bound argument."],"forward_implications":["For the dual problem, if $\\limsup n/d^2<1/4$ then with probability tending to one no vector $y$ with $\\sum_i y_i=0$ and $\\sum_i y_i x_i x_i^\\top \\succ 0$ exists, while if $\\liminf n/d^2>1/4$ such a vector exists.","In the satisfiable regime the proof produces a fit with $\\lambda_- I \\preceq S \\preceq \\lambda_+ I$ and $\\mathrm{Tr}\\,S=d$, so the semiaxes of the fitted ellipsoid stay within constant factors of the sphere's radius.","In the unsatisfiable regime the obstruction is quantitative: the empirical risk $\\frac{1}{n}\\sum_i (1-e^{-(x_i^\\top S x_i - \\mathrm{Tr}S - b)^2})$ is bounded below by a constant $e_\\gamma>0$ uniformly over all $S\\succeq0$ with $\\|S\\|_F=1$ and $|b|\\le C_\\gamma$, with probability exponentially close to one.","For a Haar-random rank-$r$ subspace of $\\mathbb{R}^N$, minimum trace factor analysis succeeds with high probability when $N-r \\ge (2+\\varepsilon)\\sqrt{N}$ and fails when $N-r \\le (2-\\varepsilon)\\sqrt{N}$.","The canonical SDP relaxation of vector discrepancy certifies no nontrivial lower bound once the equivalent ellipsoid problem becomes infeasible."],"supporting_citations":[{"why":"provides the Gaussian-comparison framework and proves the approximate threshold; this paper removes the error tolerance and the spectral restriction.","marker":"[BM25]"},{"why":"replica-method prediction of the threshold at $n=d^2/4$ and of the typical fit's spectral density, which set the sharp constant.","marker":"[MK24]"},{"why":"formulates the two-sided conjecture and proves the previous best satisfiability range.","marker":"[PTVW23]"},{"why":"gives the two-sided spectral edge for polynomial-scaling kernel matrices used for exact head corrections.","marker":"[KNH25]"},{"why":"conic integral-geometry phase transition theory that identifies the statistical dimension $d(d+1)/4$.","marker":"[ALMT14]"},{"why":"the Gaussian min-max comparison inequality used for the satisfiable-side margin.","marker":"[Gor85]"},{"why":"establishes satisfiability at a positive density and introduces the dual balanced-combination formulation.","marker":"[BMMP24]"}],"fun_headline_variants":["Ellipsoid fitting: sharp transition at d^2/4 proven","Random ellipsoid fit exists below d^2/4, almost never above","Phase transition in ellipsoid fitting precisely at n = d^2/4","Ellipsoid fit: exact boundary n = d^2/4 for random points","At d^2/4 points, random ellipsoid fitting flips from possible to impossible"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The unsatisfiable phase depends on an asserted rowwise extension of a previously proven free-entropy universality to losses with arbitrary deterministic offsets (Proposition 4.8); the paper says this extension is only sketched, and if it fails the no-fit conclusion for $n/d^2>1/4$ does not follow.","fun_headline_variants_meta":{"raw":{"variants":["Ellipsoid fitting: sharp transition at d^2/4 proven","Random ellipsoid fit exists below d^2/4, almost never above","Phase transition in ellipsoid fitting precisely at n = d^2/4","Ellipsoid fit: exact boundary n = d^2/4 for random points","At d^2/4 points, random ellipsoid fitting flips from possible to impossible"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000466,"raw_usage":{"total_tokens":2445,"prompt_tokens":1186,"completion_tokens":1259,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":802,"completion_tokens_details":{"reasoning_tokens":1165}},"tokens_in":802,"tokens_out":1259,"duration_ms":11004,"temperature":1.0,"reasoning_tokens":1165,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T04:11:28.574541+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the free-entropy comparison of Proposition 4.8 in the smallest non-degenerate case, say $n=1$, $m=2$, with a nonzero offset $a_1$ and the full Schatten-constrained set $C_m$; the proposition predicts the difference between the quadratic-chaos and GOE ground states vanishes as $m\\to\\infty$. A non-vanishing difference for any such offset would refute the bulk-universality step and with it the upper-bound theorem.","supporting_citations":[],"review_version":1}