{"id":"aac016c3-6fb5-47ab-b690-141b44436c98","arxiv_id":"2608.12415","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":9.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"Centered ellipsoid fitting of m Gaussian points in R^d has a sharp phase transition at m = (1 ± o_d(1)) d^2/4.","lead":"The paper proves that for m random Gaussian points in d dimensions, a centered ellipsoid through all m points exists with high probability when m is just below d^2/4 and does not exist when m is just above d^2/4. This resolves the ellipsoid fitting conjecture up to a vanishing factor, using explicit semidefinite witnesses built by an iterative random-matrix construction.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Deferred proof of the backtracking-residual cancellation (Prop 5.35) and the skipped summation in Prop 5.31 leave the variance-1/semicircle step uncertified; without it, the PSD witness may fail.","rationale":"Read in good faith: the paper is a serious and detailed attack on the ellipsoid fitting conjecture, with a coherent iterative construction, graph-matrix formalism, and many lemmas proved in text. The reader's CONDITIONAL verdict is appropriate. My stress-test agrees: the strongest claim cannot be certified from the submitted version because the positivity argument depends on the free-independence/semicircle result (Thm 5.18, Lemma 2.21) and its key cancellation (Prop 5.35) is deferred to a truncated appendix. I did not find a clear counterexample or internal inconsistency in the visible text; the concern is the missing formal proof of a genuinely load-bearing step, plus a skipped algebraic summation that controls the error magnitude. These are exactly the kind of gaps that can hide a factor. If the full Appendix C supplies the proof and the summation is as claimed, the central claim would be supported. Independent support in the text includes the careful treatment of the MP polynomial side (Section 4) and the explicit scalar concentration bounds, which are strong positives. No ad hominem intended; the recommendation is to condition final acceptance on completing the deferred proofs.","tokens_in":60703,"tokens_out":28462,"duration_ms":279082,"concrete_test":"Obtain the complete Appendix C and verify Prop 5.35 by an independent computation: for a variance-normalized K, derive the second-moment bound E[Tr((sum_tau c_tau^2 M_BacktrackingInt(tau) - I_d)^2)] and show it is O(d) (equivalently spectral norm o(1) whp via Claim B.8), using the LCP block-value machinery of Sec 4.4. Simultaneously, redo the summation in Prop 5.31 line-by-line, replacing the undefined tau by a supremum over shapes and making the vertex-count sums explicit; confirm that the resulting B_q(NonIdeal) has the stated form with no missing (3||c||_1)^{D_V} factor.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorems 1.1 and 1.2 are proven by explicit SDP witnesses whose positivity rests on the inner matrix Q having semicircular spectrum in [-2,2] up to o_d(1) once Var(Q)=1. This is the content of Thm 5.18 and Lemma 2.21. The proof chain has two load-bearing sub-claims that are not fully established in the submitted text. First, Prop 5.35 asserts that the backtracking intersections of a variance-normalized combination of backbone-dangling shapes collapse to I_d: sum_tau c_tau^2 M_BacktrackingInt(tau) - I_d = o_d(1) in spectral norm. The text gives only a 'Proof Sketch' and defers the formal argument to Section C, which is cut off in the visible manuscript. This cancellation is what removes the identity term in P_j(Q) so that the Chebyshev polynomial is approximated by proper concatenations; if the residual is not o_d(1), the affine-deviation invariant (Prop 2.3) acquires a nonvanishing diagonal term and the final matrix fails either the constraints or PSDness. Second, the quantitative bound in Thm 5.18 and the calculation in Prop 5.31 contain an undefined 'B_q(NonIdeal)' and a skipped summation: the displayed line replaces a sum over shapes of |c(tau)| (3||c||_1)^{|V(tau)|} with a constant factor, but the missing intermediate step is exactly where the dependence on the maximum shape size D_V is controlled. Without seeing that summation, the advertised d^{-1/2+o(1)} error is not verifiable. These are not cosmetic issues: they are the precise places where the graph-matrix analysis could break.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper claims to resolve the ellipsoid fitting conjecture up to a vanishing factor: for m independent Gaussian points in R^d, with high probability there is a centered ellipsoid through all points when m ≤ (1-o_d(1)) d^2/4, and no such ellipsoid when m ≥ (1+o_d(1)) d^2/4, with o_d(1) instantiated as 1/poly(log log d). The proof constructs explicit primal and dual SDP witnesses via an iterative process. The inner matrix Q is built from graph matrices of backbone-dangling shapes; the key technical steps are: (1) a Marchenko-Pastur analysis of the Gram matrix M and its inverse; (2) a semicircular spectrum theorem for linear combinations of backbone-dangling shapes with variance 1; (3) a truncation scheme showing that variance-1 and positivity are preserved at the chosen parameters.","tokens_in":61090,"tokens_out":9464,"duration_ms":85151,"significance":"If correct, this resolves a conjecture posed by Saunderson, Chandrasekaran, Parrilo, and Willsky and sharpens a line of work that previously achieved constant-factor thresholds. The proof is constructive and explicit, with concrete formulas for the correction primitive, variance recursions, and parameter choices (e.g., D=t*=(log log d)^a, δ=D^{-1/2}), which is a strength: the construction is not merely existential, and the threshold d^2/4 arises from the fixed-point equation for Var(Q), not from fitting constants to the target. However, the manuscript currently defers or sketches two load-bearing technical steps (the backtracking-residual cancellation for semicircle polynomials and the quantitative bound for non-ideal steps in the norm theorem), which prevents verification of the main theorems as submitted.","major_comments":[{"comment":"This proposition is load-bearing for the semicircular/Chebyshev step. It asserts that the backtracking intersections of a variance-normalized combination of backbone-dangling shapes collapse to identity: ∥∑_τ c_τ^2 M_{BacktrackingInt(τ)} - I_d∥_sp = o_d(1). The proof is only a two-sentence sketch, and the formal proof is deferred to Section C, which is not present in the visible manuscript (the visible text stops at 'Proposition C.1(Backtracking Residual for S...'). This cancellation is what removes the identity term in P_j(Q) (Lemma 5.33), so that the Chebyshev polynomial is approximated by proper concatenations (Theorem 5.32, Lemma 2.21). If the residual is not o_d(1), the affine-deviation invariant (Prop 2.3) acquires a nonvanishing diagonal term and the final witness Λ may fail PSDness. This step must be proved in the submitted text.","section":"§5.6, Prop. 5.35"},{"comment":"The quantitative norm bound for non-ideal steps is not verifiable as written. The definition of B_q(NonIdeal) in Theorem 5.18 contains quantities |V(τ)|, c(τ), and |V(τ_i)| that are not specified as a maximum or a summation; Proposition 5.31's proof has a skipped summation where the sum over shapes of |c(τ)|(3∥c∥_1)^{|V(τ)|} is replaced by a constant factor, and the missing intermediate step is exactly where the dependence on D_V is controlled. Without that summation, the advertised d^{-1/2+o(1)} error term and hence the bound ∥K∥_sp ≤ 2+o_d(1) for Var(K)=1 is unsupported. This norm bound is then used to assert the semicircular spectrum of Q and to control the error terms in the final truncation analysis; the gap is load-bearing.","section":"§5.4, Prop. 5.31 and Thm. 5.18"},{"comment":"The variance identity Var(correct(τ)) = γ/(1-γ) Var(τ) + o_d(1) drives the scalar recursion that yields Var(Q)=1 at γ=1/2 (Lemma 2.24 and the display in §2.5). However, the proof of Lemma 5.1 is explicitly a sketch: it notes that it has not incorporated polynomial truncation of M^{-1}, it relies on Proposition 5.9 (local charging) whose full analysis is deferred to the appendix, and it asserts without full detail that non-well-behaved vertical intersections have o_d(1) norm. Since the variance normalization is what pins the semicircle radius to 1 and hence the threshold at γ=1/2, the complete block-value argument (including the interaction with truncation) needs to appear.","section":"§5.1, Lemma 5.1"}],"minor_comments":[{"comment":"The text contains the unresolved placeholder 'as we will discuss in ***' which should be replaced with a proper cross-reference.","section":"§3.2"},{"comment":"The notation S_i^j is used for (S_i)^j without definition; please define it at first use.","section":"§2.5"},{"comment":"Claim 6.10 states the size bound for D=t^*=(\\log d)^a, while the parameter choice two paragraphs earlier is D=t^*=\\lceil(\\log\\log d)^a\\rceil; state the constraint a<1 explicitly, as it is needed for D_V=d^{o(1)} and for Remark 6.13's condition.","section":"§6.4"},{"comment":"The condition 'D ≤ c log log d / log log log d' should be reconciled with the chosen D=(log log d)^a; the text should state that a<1 is required.","section":"Remark 6.13"},{"comment":"The reference list includes [KS26] and [MW26] as 'manuscript communicated privately'; if these are to be relied upon, the authors should indicate which parts of the present proof depend on them or clarify that the results are independent.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is technically ambitious and the main results would be a major advance. However, the visible text omits the proof of Proposition 5.35 (deferred to a missing Section C) and leaves the summation in Proposition 5.31 unfinished; these are exactly the steps that certify the variance-1/semicircle spectrum of Q. I recommend requesting a revision that includes the complete deferred sections and the completed summation, and that clarifies the parameter constraints in §6.4. The presence of concurrent works [KS26, MW26] should also be disclosed more precisely regarding any overlap."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe short version: this paper claims, and plausibly proves, the sharp d^2/4 phase transition for ellipsoid fitting, in both directions, up to o_d(1) slack. If the two main theorems are right, that settles the Saunderson et al. conjecture up to a vanishing factor. That would be a genuine breakthrough. Prior work only reached m ≤ c d^2 with a tiny constant c or d^2/polylog(d), and impossibility only at d^2/2. The construction is explicit: an iterative SDP witness built from graph matrices, extending Potechin-Xu's Lovász theta work. The variance recurrence at γ=1/2 is clean and self-consistent, and the dual refutation mirrors the primal correction almost exactly. This is a serious paper and the authors are honest about concurrent work and about what is deferred.\n\nBut the submitted text is not yet a complete proof. Two load-bearing steps are deferred or partially defined. Proposition 5.35, which states that the backtracking residual collapses to the identity up to o_d(1), is given only as a proof sketch with the formal argument pushed to Section C — and Section C is cut off in this version. That cancellation is what makes the Chebyshev polynomial agree with proper concatenations of backbone-dangling shapes; without it, the PSD witness can fail. Similarly, Proposition 5.31 defines an auxiliary B_q(NonIdeal) and then jumps over a summation over shapes to a bound; the skipped intermediate step is exactly where the dependence on maximum shape size D_V is controlled. The displayed line is not verifiable as written. I also noticed a placeholder in Section 3.2 ('as we will discuss in ***'), which suggests the manuscript was not fully polished.\n\nTo be clear: I don't think the main claims are wrong. The high-level architecture is coherent, the variance fixed point at 1 is computed from first principles, and the citation pattern looks fair. The problem is certification: the central positivity step is not backed by a complete argument in this version. A referee could not accept the theorems as proven from the submitted PDF.\n\nWho is this for? Anyone working on ellipsoid fitting, SoS lower bounds, or graph-matrix methods. The technique section is worth reading even if the formal details are pending. I'd send it to a serious referee, with the expectation that the authors complete Section C and the missing summation in Prop 5.31 before it can be accepted.\n\nRecommendation: engage with it, but treat the two theorems as claims under construction, not established results. If the deferred proofs check out, this is a major paper.","headline":"Plausible resolution of the ellipsoid fitting threshold at d^2/4, but the submitted version is not fully verifiable because the key semicircle/positivity step is deferred to a missing appendix.","tokens_in":61665,"tokens_out":3905,"would_cite":true,"duration_ms":38431,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60B20","90C22","52A20","60D05"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper proves a sharp phase transition for ellipsoid fitting: with high probability a centered ellipsoid exists exactly up to $m = (1 \\pm o_d(1)) d^2/4$.","keywords":["ellipsoid fitting","phase transition","Gaussian random points","semidefinite programming","graph matrices","orthogonal polynomials","free independence","Marchenko-Pastur distribution"],"falsifier":"Concretely, one could run the paper's truncated iterative construction for a large instance, say $d = 10^5$ and $m = \\lfloor d^2/4 \\rfloor$ with $D = (\\log\\log d)^a$ and $\\delta = D^{-1/2}$, and compute the smallest eigenvalue of $\\Lambda = (1/C_\\delta) F_\\delta^{\\leq D}(Q_*) + D_E$; the proof predicts it is at least $\\Omega(\\delta) > 0$. A negative eigenvalue of magnitude not $o_d(1)$ would falsify Theorem 1.1. Equivalently, one can compute the low-order trace moments of $Q_*$ at $\\gamma = 1/2$ and compare them with the semicircle moments of variance 1.","tokens_in":60511,"feed_emoji":"📐","tokens_out":8950,"duration_ms":86519,"temperature":0.7,"pith_summary":"This paper proves that ellipsoid fitting has a sharp phase transition: for $m$ independent standard Gaussian points in dimension $d$, a centered ellipsoid through all of them exists with high probability when $m \\leq (1-o_d(1)) d^2/4$, and no such ellipsoid exists when $m \\geq (1+o_d(1)) d^2/4$, where the $o_d(1)$ terms are of order $1/\\mathrm{poly}(\\log\\log d)$. This settles the ellipsoid fitting conjecture up to a vanishing factor. The result matters because the positive-semidefiniteness constraint halves the naive dimension count: the space of $d\\times d$ symmetric matrices has dimension about $d^2/2$, and the conjecture says the true feasibility threshold is exactly half of that count. Both directions are established by explicitly constructing SDP witnesses, not by counting arguments.","feed_headline":"Ellipsoid fitting flips sharply at m = d^2/4","feed_subtitle":"Both feasibility and refutation now have explicit witnesses up to a 1/poly(log log d) factor.","key_machinery":"The argument is carried by graph matrices and an equivalence between orthogonal polynomials and shape concatenation. A linear combination $K$ of backbone-dangling shapes with $\\mathrm{Var}(K) = 1$ is shown to have semicircular spectrum in $[-2, 2]$ up to $o_d(1)$, and its Chebyshev polynomial $P_t(K)$ is approximated, up to $o_d(1)$ in spectral norm, by the sum of graph matrices of all $t$-fold proper concatenations of the shapes in $K$. The same correspondence, with Marchenko-Pastur orthogonal polynomials in place of Chebyshev polynomials, gives an explicit inverse $A^{-1}$ of the main component of the Gram matrix $M$. The correction primitive $\\mathrm{correct}(H) = \\frac{1}{1-\\gamma}(-L^{*}M^{-1}L(H) + \\gamma H)$ removes the non-free term $\\gamma H$ that a naive projection correction would introduce, and a scalar variance recurrence forces $\\mathrm{Var}(Q) = 1$ at $\\gamma = 1/2$. A shifted positive function $F_\\delta$ with $\\gamma = 1/2 - \\Theta(\\delta)$ then supplies a positive spectral floor that dominates all truncation and early-termination errors.","core_discovery":"Concretely, the paper proves that with probability $1-o_d(1)$, feasibility of fitting a centered ellipsoid through $m$ independent $\\mathcal{N}(0, I_d/d)$ points flips at $m = d^2/4$. Below the threshold the witness is a positive semidefinite matrix $\\Lambda$ with $v_i^{\\top}\\Lambda v_i = 1$ for every point $v_i$, built by iteratively correcting the affine deviations of a spectrally transformed inner matrix $Q$. Above the threshold a dual matrix $\\Lambda \\in \\mathrm{span}\\{v_i v_i^{\\top} : i \\in [m]\\}$ with $\\langle \\Lambda, I - R \\rangle < 0$ rules out any such ellipsoid. The authors describe this as resolving the ellipsoid fitting conjecture up to a vanishing factor, with $o_d(1)$ instantiated as $1/\\mathrm{poly}(\\log\\log d)$, and note that two concurrent works obtain comparable results.","pith_inferences":["A testable finite-size extension: for fixed $d$, scanning $m$ across $d^2/4$, the smallest eigenvalue of the explicit primal witness should cross zero at $m/d^2 = 1/4 \\pm O(1/\\mathrm{poly}(\\log\\log d))$; such simulations could probe whether the $1/\\mathrm{poly}(\\log\\log d)$ slack is tight or an artifact of the proof.","The correction primitive — subtracting the correlated $\\gamma M_\\tau$ term before iterating — suggests a general recipe for sharp constants in other SDP feasibility problems whose random constraint matrices combine a low-rank term with a Wishart-like component.","Because the variance fixed point at $\\gamma = 1/2$ only uses the Chebyshev coefficient identity $\\sum_{j\\geq 2} b_j^2 = 1 - C_F^2$, the construction may generalize to a family of nonnegative spectral functions $F$, yielding nearby sharp thresholds for related fitting problems."],"forward_implications":["Below $m = (1-o_d(1)) d^2/4$, the fitted ellipsoid can be produced by an explicit iterative algorithm with polynomial truncations, rather than shown to exist only non-constructively.","Above $m = (1+o_d(1)) d^2/4$, the dual witness certifies infeasibility, so both sides of the transition are witnessed by explicit SDP solutions.","The threshold $d^2/4$ confirms that the positive-semidefinite constraint imposes exactly a factor-two loss relative to the naive dimension count $d^2/2$.","The vanishing slack of $1/\\mathrm{poly}(\\log\\log d)$ means the transition is sharp up to a very slowly growing factor; the paper makes no attempt to optimize this factor."],"supporting_citations":[{"why":"Introduced the ellipsoid fitting problem and conjectured the sharp transition at $d^2/4$; the statement this paper resolves up to a vanishing factor.","marker":"[SCPW12]"},{"why":"Supplied the iterative construction, the graph-matrix/orthogonal-polynomial machinery, and the variance fixed-point scheme that the present proof adapts.","marker":"[PX26]"},{"why":"Provided the identity-perturbation base, the decomposition of the Gram matrix $M = A + B$, and the backbone-dangling shape framework used for the initialization.","marker":"[HKPX23]"},{"why":"Gave near-optimal feasibility $d^2/\\mathrm{polylog}(d)$ via identity perturbation with an expansion of $A^{-1}$, the starting point for the initialization $Q_0$.","marker":"[PTVW22]"},{"why":"Established a comparable $d^2/\\mathrm{polylog}(d)$ feasibility bound and the Woodbury-based inverse formula for $M$ that the present proof sharpens.","marker":"[KD22]"},{"why":"Provided the replica-method prediction of the transition at $d^2/4$, including the half-zero-eigenvalue structure that the construction matches.","marker":"[MK24]"},{"why":"The Woodbury identity used to pass from the inverse of $A$ to the inverse of $M$.","marker":"[Woo50]"},{"why":"A general spectral theorem for kernel random matrices that the paper notes also yields the needed Marchenko-Pastur spectrum of $A$.","marker":"[KNH25]"}],"fun_headline_variants":["Ellipsoid fitting: sharp phase transition at d^2/4","Conjecture settled: ellipsoid fitting flips at d^2/4","Ellipsoid fitting: both sides witnessed at m=d^2/4","Sharp threshold for ellipsoid fitting: m equals d^2/4"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole construction depends on the claim that the iteratively built inner matrix has a semicircular eigenvalue distribution on $[-2,2]$ and total variance 1 up to errors vanishing as $d$ grows; if that spectral and variance control fails at even a vanishing scale, the final matrix $\\Lambda$ may fail to be positive semidefinite and the ellipsoid witness collapses.","fun_headline_variants_meta":{"raw":{"variants":["Ellipsoid fitting: sharp phase transition at d^2/4","Conjecture settled: ellipsoid fitting flips at d^2/4","Ellipsoid fitting: both sides witnessed at m=d^2/4","Sharp threshold for ellipsoid fitting: m equals d^2/4"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000409,"raw_usage":{"total_tokens":2081,"prompt_tokens":862,"completion_tokens":1219,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":478,"completion_tokens_details":{"reasoning_tokens":1135}},"tokens_in":478,"tokens_out":1219,"duration_ms":12507,"temperature":1.0,"reasoning_tokens":1135,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:33:33.753830+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Concretely, one could run the paper's truncated iterative construction for a large instance, say $d = 10^5$ and $m = \\lfloor d^2/4 \\rfloor$ with $D = (\\log\\log d)^a$ and $\\delta = D^{-1/2}$, and compute the smallest eigenvalue of $\\Lambda = (1/C_\\delta) F_\\delta^{\\leq D}(Q_*) + D_E$; the proof predicts it is at least $\\Omega(\\delta) > 0$. A negative eigenvalue of magnitude not $o_d(1)$ would falsify Theorem 1.1. Equivalently, one can compute the low-order trace moments of $Q_*$ at $\\gamma = 1/2$ and compare them with the semicircle moments of variance 1.","supporting_citations":[],"review_version":1}