Finite-Accuracy Lower Bounds

For every admissible finite dimension, rank and accuracy, this note proves $q_{\mathrm{sp}}(n,k,\varepsilon)\ge c\,\frac{k}{\sqrt\varepsilon}\log\bigl(1+\frac{n\sqrt\varepsilon}{k}\bigr)$ with a universal positive constant $c$. The argument uses a determinant tilt of a singular Wishart law, its exact posterior under adaptive matrix–vector queries, and an integration-by-parts estimate on a Grassmann manifold, which bounds the growth per query of a regularized log-determinant of the hidden-kernel overlap. The finite-dimensional spectral input is the least-singular-value theorem of Rudelson and Vershynin; no deformed-Wigner dimension restriction is used. Together with an upper bound reproduced from earlier work, this gives $\Theta(\sqrt n\log n)$ at $k=1$, $\varepsilon=1/n$, and $\Theta(n)$ whenever $\varepsilon\le(k/n)^2$. It also gives matching universal-constant bounds throughout $\varepsilon\ge k/n$. A logarithmic transition remains: at $k=1$, $\varepsilon=(\log n/n)^2$, the bounds are $\Omega(n\log\log n/\log n)$ and $O(n)$.