Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting

The factorization norms of the lower-triangular all-ones n × n matrix, γ2(Mcount) and γF(Mcount), play a central role in differential privacy as they are used to give theoretical justification of the accuracy of the only known production-level private training algorithm of deep neural networks by Google. Prior to this work, the best known upper bound on γ2(Mcount) was 1 + fraclog nπ by Mathias (Linear Algebra and Applications, 1993), and the best known lower bound was frac1π(2 + log(frac2n+13)) ≈ 0.507 + fraclog nπ (Matouvsek, Nikolov, Talwar, IMRN 2020), where log denotes the natural logarithm. Recently, Henzinger and Upadhyay (SODA 2025) gave the first explicit factorization that meets the bound of Mathias (1993) and asked whether there exists an explicit factorization that improves on Mathias' bound. We answer this question in the affirmative. Additionally, we improve the lower bound significantly. More specifically, we show that 0.701 + fraclog nπ + o(1) ;≤; γ2(Mcount) ;≤; 0.846 + fraclog nπ + o(1). That is, we reduce the gap between the upper and lower bound to 0.14 + o(1). We also show that our factors achieve a better upper bound for γF(Mcount) compared to prior work, and we establish an improved lower bound: 0.701 + fraclog nπ + o(1) ;≤; γF(Mcount) ;≤; 0.748 + fraclog nπ + o(1). That is, the gap between the lower and upper bound provided by our explicit factorization is 0.047 + o(1).