The sharp SAT/UNSAT phase transition in random ellipsoid fitting

Let x_1,\ldots,x_n be independent standard Gaussian vectors in \mathbb{R}^d. An ellipsoid fit is a matrix S \succeq 0 such that x_i^\top S x_i =d for every i, so that all the points lie on the boundary of the centered ellipsoid { x : x^\top S x = d}. Saunderson, Parrilo and Willsky conjectured that, as n,d \to \infty, this semidefinite feasibility problem undergoes a sharp transition at n \sim d^2/4. We prove this conjecture. If \lim \sup n/d^2 = α^* <1/4, then, with probability tending to one, an ellipsoid fit exists; moreover, one can choose S with all eigenvalues in a fixed interval [λ_- , λ_+] \subset (0,\infty) depending only on α^*. Conversely, if \lim \inf n/d^2 > 1/4, then, with probability tending to one, no ellipsoid fit exists, without any spectral restriction. Our proof builds on the Gaussian-equivalence framework developed by Bandeira and Maillard (2025) and closes the two gaps left open in their work: establishing exact fitting and removing the operator-norm constraint. On the satisfiable side, the new ingredients are a head-tail decomposition of the dual vector, exact correction of the sparse head constraints, and a Gaussian comparison principle for the low-influence tail. On the unsatisfiable side, we split a candidate into a low-rank spectral head and a Schatten-3 diffuse bulk, Gaussianize the bulk conditionally on the head, and apply a projected Gordon escape argument. The threshold is governed by the statistical dimension d(d+1)/4 of the positive semidefinite cone.