← Back to arXiv
arXivProbabilityarXiv:2608.12415

Sharp Phase Transition for Ellipsoid Fitting

The paper solves a long-standing mathematical conjecture about fitting ellipsoids to random points in high-dimensional space. An ellipsoid is a generalized version of an oval or egg shape, and the question is: given a cloud of randomly placed points in a space with many dimensions, when can you find an ellipsoid centered at the origin that passes exactly through all of them? The conjecture, originally posed by four researchers, predicted that there should be a sharp threshold governing whether this is possible or not.

The main finding is that the critical threshold is exactly the number of points equal to one quarter of the square of the number of dimensions. Below this threshold, you can almost always find such an ellipsoid; above it, you almost certainly cannot. The word "sharp" here is important: the transition between possible and impossible happens in a very narrow window rather than being a gradual change. This confirms the original conjecture almost exactly, with only a tiny error term that shrinks as the dimension grows large.

Results like this belong to a broader family of "phase transition" phenomena in mathematics and statistics, similar in spirit to how water suddenly freezes at a specific temperature rather than gradually becoming more solid. They matter because they tell researchers precisely how much data or how many constraints a system can handle before a problem fundamentally changes character. For practical applications, understanding these thresholds informs fields like signal processing, machine learning, and optimization, where fitting geometric shapes to data is a common task.

Read original →