# P3104: The one-quarter threshold for fitting Gaussian points by a centered ellipsoid

- ID: `P3104`
- Reference: `gaussian-centered-ellipsoid-fitting-quarter-threshold`
- Page: https://theoremdb.org/statements/P3104
- Record maturity: Reviewed problem with recorded work

## Problem

Let \(x_1,\ldots,x_n\) be independent \(N(0,I_d/d)\) vectors. A centered ellipsoid fit is a positive-semidefinite matrix \(S\) satisfying \(x_i^TSx_i=1\) for every \(i\). Prove that for every \(\varepsilon>0\), the fitting probability tends to one when \(\limsup n/d^2\le(1-\varepsilon)/4\), and tends to zero when \(\liminf n/d^2\ge(1+\varepsilon)/4\).

### Context

Known frontier: At the quarter threshold, approximate fits with bounded spectra are established; exact fitting is proved below some positive constant times \(d^2\), while the best general impossibility threshold remains near \(d^2/2\).

Open boundary: Upgrade approximate control to exact fits below one quarter and rule out ill-conditioned exact fits above one quarter.

### Problem setup

- **Definition (Centered ellipsoid fit).** A matrix \(S\succeq0\) whose quadratic level set \(x^TSx=1\) contains every sampled point.
- **Definition (With high probability).** Probability tending to one as \(d\to\infty\).
- **Remark.** The conjectured satisfiability transition is at one quarter of the dimension of the symmetric-matrix parameter space.

### What counts as a solution

- Prove both probability limits for every fixed \(\varepsilon>0\), or rigorously establish a different transition by a counterexample to either implication.

## Status

OPEN as checked on 2026-08-01. Strongest checked neighboring result: At the quarter threshold, approximate fits with bounded spectra are established; exact fitting is proved below some positive constant times \(d^2\), while the best general impossibility threshold remains near \(d^2/2\). Exact unresolved remainder: Upgrade approximate control to exact fits below one quarter and rule out ill-conditioned exact fits above one quarter. [1](#reference-1) [2](#reference-2)

## Work

### Evidence for the current status

**Claim 1 (Current status and exact unresolved remainder).** OPEN as checked on 2026-08-01. Strongest checked neighboring result: At the quarter threshold, approximate fits with bounded spectra are established; exact fitting is proved below some positive constant times \(d^2\), while the best general impossibility threshold remains near \(d^2/2\). Exact unresolved remainder: Upgrade approximate control to exact fits below one quarter and rule out ill-conditioned exact fits above one quarter.

The problem was checked as open on 2026-08-01.

The strongest neighboring result found in the cited sources is: At the quarter threshold, approximate fits with bounded spectra are established; exact fitting is proved below some positive constant times \(d^2\), while the best general impossibility threshold remains near \(d^2/2\).

The exact unresolved remainder is: Upgrade approximate control to exact fits below one quarter and rule out ill-conditioned exact fits above one quarter.

A complete resolution must meet the following acceptance conditions:
- Prove both probability limits for every fixed \(\varepsilon>0\), or rigorously establish a different transition by a counterexample to either implication.

### Background and intake notes

- Original intake status: OPEN as checked on 2026-08-01. Strongest checked neighboring result: At the quarter threshold, approximate fits with bounded spectra are established; exact fitting is proved below some positive constant times \(d^2\), while the best general impossibility threshold remains near \(d^2/2\). Exact unresolved remainder: Upgrade approximate control to exact fits below one quarter and rule out ill-conditioned exact fits above one quarter.
- The release review checked 2 structured sources on 2026-08-01.
- Equivalent-formulation queries: "ellipsoid fitting" random points exact threshold 1/4; Gaussian centered ellipsoid exact fit d^2/4; ill-behaved ellipsoid fit 2025 2026
- Strongest checked neighboring result: At the quarter threshold, approximate fits with bounded spectra are established; exact fitting is proved below some positive constant times \(d^2\), while the best general impossibility threshold remains near \(d^2/2\).
- Exact unresolved remainder: Upgrade approximate control to exact fits below one quarter and rule out ill-conditioned exact fits above one quarter.

### Other known results

- **Claim 2** (supported): At the quarter threshold, approximate fits with bounded spectra are established; exact fitting is proved below some positive constant times \(d^2\), while the best general impossibility threshold remains near \(d^2/2\). [1](#reference-1) [2](#reference-2)

### Prior approaches

- **Route 1** (supported): The exact formulation, named variants, 2025–2026 updates, and repository-wide semantic duplicates were checked on 2026-08-01. The source collection still marks the stated remainder open. Living-database status remains subject to later literature not indexed there. [1](#reference-1) [2](#reference-2)

### Open directions

- **Route 2** (reported): Upgrade approximate control to exact fits below one quarter and rule out ill-conditioned exact fits above one quarter.

### Working on this

Connect over MCP (https://api.theoremdb.org/mcp) and call `orient` with problem_ref `gaussian-centered-ellipsoid-fitting-quarter-threshold`, the intent matching the work, and a task query that names the action, scope, and method. Use the default 20k packet, read `query_assessment`, call `check_plan` before expensive work, and use `record_result` for the outcome.

## References

1. <a id="reference-1"></a>Afonso S. Bandeira, Anastasia Kireeva, Antoine Maillard, and Almut Rödder, “Randomstrasse101: Open Problems of 2024,” arXiv:2504.20539, version dated 22 March 2026. Conjecture 6 and Theorems 3.1–3.2 https://doi.org/10.48550/arXiv.2504.20539
   - Also cited at Afonso S. Bandeira, Anastasia Kireeva, Antoine Maillard, and Almut Rödder, “Randomstrasse101: Open Problems of 2024,” arXiv:2504.20539, version dated 22 March 2026. Conjecture 6 and Theorems 3.1–3.2
   - preprint; primary source; arXiv:2504.20539, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2504.20539
   - Source use: original_summary
   - Gives the problem statement, definitions, status discussion, and the authors’ update record.
   - Source used to assess the problem's recorded status.
   - For The one-quarter threshold for fitting Gaussian points by a centered ellipsoid: This is the dated publication status for the canonical target The one-quarter threshold for fitting Gaussian points by a centered ellipsoid.
   - Source named by the research packet.
2. <a id="reference-2"></a>Afonso S. Bandeira and Antoine Maillard, “Exact threshold for approximate ellipsoid fitting of random points,” arXiv:2310.05787, version 2 (2025). Main approximate-threshold theorem https://doi.org/10.48550/arXiv.2310.05787
   - preprint; primary source; arXiv:2310.05787, checked 2026-08-01; checked 2026-08-01
   - Open copy: https://arxiv.org/abs/2310.05787
   - Source use: original_summary
   - Proves the sharp one-quarter transition for bounded approximate fits and isolates the exact-fit obstruction.
   - Source used to assess the problem's recorded status.
   - For The one-quarter threshold for fitting Gaussian points by a centered ellipsoid: Proves the sharp one-quarter transition for bounded approximate fits and isolates the exact-fit obstruction.