Linear Systems and Eigenvalue Problems — Problem 36

Definitions and mathematical statement

The supplied record attributes the following conjecture to Nelson--Nguyen. Its SparseStack distribution and its convention for subspace distortion are not defined in the supplied material.

For clarity, a possible formal framework is as follows. Let $V,W$ be specified finite-dimensional normed spaces over a specified field, let $r$ be a positive integer with $r\leq\dim V$, and let $S:V\to W$ be a random linear map whose distribution does not depend on the subspace being embedded. Under a norm-distortion convention, an oblivious subspace embedding with distortion parameters $\alpha,\beta$ and failure parameter $\delta\in(0,1)$ satisfies \[ \text{for every fixed subspace }E\subseteq V\text{ with }\dim E=r,\qquad \Pr_S\!\left[\forall x\in E,\ \alpha\lVert x\rVert_V\leq\lVert Sx\rVert_W\leq\beta\lVert x\rVert_V\right]\geq 1-\delta. \] The universal quantifier over subspaces is outside the probability: the distribution is independent of the chosen subspace. If the source instead uses squared-norm distortion, the inequalities inside this event must be replaced by \[ \alpha\lVert x\rVert_V^2\leq\lVert Sx\rVert_W^2\leq\beta\lVert x\rVert_V^2. \] These conventions give different assertions for the same numerical values of $\alpha,\beta$; the supplied record does not select between them. The spaces, field, norms, and failure parameter in this framework are placeholders, not additional source hypotheses.

The source assertion to prove or disprove is that a SparseStack embedding with parameters \[ \zeta=\mathcal O\!\left(\frac{\log r}{\varepsilon}\right),\qquad k=\mathcal O\!\left(\frac{r}{\varepsilon^2}\right) \] is an oblivious subspace embedding with \[ \alpha=1-\varepsilon,\qquad \beta=1+\varepsilon. \] The supplied record does not define the SparseStack random matrix, its normalization, or the roles of $\zeta$ and $k$. It also omits the admissible ranges of $r,\varepsilon$, the ambient dimensions, the required success probability, and the uniformity of the implied constants. Consequently, the displayed source assertion cannot yet be converted into a fully specified conjecture. In particular, the logarithmic bound requires clarification at $r=1$ if that case is intended to be included.

Short English statement

The Nelson--Nguyen conjecture asks whether SparseStack embeddings with $\zeta=\mathcal O((\log r)/\varepsilon)$ and $k=\mathcal O(r/\varepsilon^2)$ give oblivious subspace embeddings with distortion parameters $1-\varepsilon$ and $1+\varepsilon$. The supplied record lacks the random-matrix construction and several defining conventions, so this remains an incomplete statement requiring source clarification.

Sources

• Local UnsolvedMath registry: permanent ID $800527$, source problem code catalogue entry, title Linear Systems and Eigenvalue Problems --- Problem 36. The supplied registry labels the problem open; this label is not an independently verified mathematical or literature assessment.
• Amsel, Baumann et al., Linear Systems and Eigenvalue Problems: Open Questions from a Simons Workshop (2026), Problem 36. Supplied source URL: https://arxiv.org/abs/2602.05394. The record reports access on 2026-10-16 and extraction by arxiv_latex; those provenance details are supplied and were not independently verified here.
• Supplied attribution/context: Nelson--Nguyen conjecture, concerning subspace embedding properties of sparse random matrices. No separate original Nelson--Nguyen reference is supplied.