ChatGPT 5.6 Sol-Originated Idea Gives a Near-Optimal Lower Bound for ℓp Subspace Embeddings

In a preprint first uploaded on August 14, 2026, Yi Li establishes a near-optimal dimension lower bound for low-distortion $\ell_p$-subspace embeddings. For every fixed $p\geq1$ that is not an even integer, and $d$ at least a constant multiple of $\log(1/\epsilon)$, the paper proves

$$N_p(d,\epsilon)\gtrsim_p \frac{d}{\epsilon^2\operatorname{polylog}(d/\epsilon)}.$$

The result improves the previous lower bound, which lacked the factor of $d$, and is optimal up to logarithmic factors for $1\leq p<2$. The proof develops a hard instance for the for-all $\ell_p$-subspace sketch problem, derives a bit lower bound, and converts it into the embedding-dimension lower bound. For $p>2$, the larger target dependence $\widetilde{\Omega}(d^{p/2}/\epsilon^2)$ remains open.

Li states that the central technical idea originated from ChatGPT 5.6 Sol. He reports substantially revising and completing the AI-assisted material and taking responsibility for the mathematical claims, proofs, references, and final manuscript.