A Near-Optimal Lower Bound for Prefix-Matrix Factorizations

For the n× n lower-triangular all-ones matrix Q, we prove a near-optimal lower bound [ γ2,1(Q) := infQ=AB |A|2→∞|B|1→1 = Omega!left( fraclog3/2n(loglog n)3/2 right), ] where the infimum ranges over real factorizations of arbitrary finite inner dimension. This cost is a central parameter in space bounds for factorization-based rank and quantile estimation in turnstile streams and in error bounds for matrix mechanisms for continual counting under pure differential privacy. The proof combines right-sided Haar projections with a scale-dependent numerical-sparsity decomposition of the rows of B. At each scale, a rank--Frobenius argument shows that the numerically sparse rows cannot account for all of the required Schatten 2/3 mass, while a Haar projection estimate bounds the contribution of the remaining rows. Summing these bounds over the dyadic scales yields the result. The proof was obtained using a fully automated Gemini-based agentic system developed internally at Google. The authors verified the proof and made minor revisions.