arXiv CSopen access

Costs of Arbitrary Real Matrix Factorizations for Pure-DP Continual Counting

C OSTS OF A RBITRARY R EAL M ATRIX FACTORIZATIONS FOR P URE -DP C ONTINUAL C OUNTING A P REPRINT Awnon Bhowmik

Mahmudul Hasan

Department of Engineering and Computer Science Colorado Technical University [email protected]

Department of Mathematics University of Dhaka [email protected]

arXiv:2607.28703v1 [cs.CR] 30 Jul 2026

A BSTRACT Let Tn be the lower-triangular prefix-sum matrix and let cF (Tn ) and c2 (Tn ) be the factorization costs that govern mean and maximum per-coordinate squared error of the Laplace matrix mechanism under
pure ε-differential privacy, for ε > 0. We prove cF (Tn ), c2 (Tn ) = Θ (log(n + 1))3/2 with no sign, sparsity, or squareness restriction and with arbitrary finite inner dimension. Consequently, within the pure-ε-DP matrix-mechanism class the optimized maximum and mean squared errors are both Θ(ε−2 log3 (n + 1)). Under the factorization contract of Arkhipov and Kalinin (arXiv:2607.08963v1), who prove the matching lower order for factors with entries in {0, 1} and state the arbitrary-factor extension as open, the theorem below establishes the order for arbitrary real factors. The lower bound runs through a p-nuclear obstruction: an aggregate column-width estimate Dk (Tn ) ≍ n3/2 k −1/2 , valid in the low-rank range 1 ≤ k ≤ n/16, for the prefix chain, fed into the classical approximationspace conversion of Pietsch and Hinrichs–Pietsch, becomes harmonic at the critical exponent p = 2/3, and Hölder’s inequality transfers it to both factorization costs. The same computation determines np (Tn ) for each fixed 0 < p < 1: order n below 2/3, n log n at 2/3, and n3p/2 above. A Fenwick interval factorization supplies matching upper bounds. The claims are confined to pure-ε-DP Laplace matrix mechanisms and the two stated squared-error criteria; they do not cover non-matrix continual mechanisms, approximate-DP sensitivity, or expected maxima across coordinates. Keywords: continual counting; differential privacy; matrix mechanisms; operator ideals; p-nuclearity; approximation numbers.

1

Introduction

Continual counting releases every prefix sum of a stream while protecting each update [7, 4]. For a horizon n, the workload is the lower-triangular matrix Tn (i, j) = 1{j ≤ i}, 1 ≤ i, j ≤ n. (1.1) A matrix mechanism [16] factors this workload as Tn = LR, adds independent noise to Rx, and reconstructs the prefix answers with L. Under pure ε-differential privacy and unit ℓ1 adjacency the relevant sensitivity of R is ∥R∥1→1 , the largest ℓ1 norm of a column (Lemma 3.2), and the Laplace mechanism calibrated to it is ε-differentially private (Proposition 3.3). Two factorization costs therefore arise: ∥L∥F √ ∥R∥1→1 , cF (Tn ) = inf (1.2) Tn =LR n c2 (Tn ) = inf ∥L∥2→∞ ∥R∥1→1 . (1.3) Tn =LR

The infima range over arbitrary finite inner dimensions and arbitrary real factors; these are the two costs of Arkhipov and Kalinin [2, eqs. (5)–(6)]. Arkhipov and Kalinin prove upper bounds of order (log n)3/2 for both costs. They also prove matching lower bounds when both factors have entries in {0, 1}, and their arXiv v1 closes by stating that extending the lower bound to arbitrary

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

matrix factorizations remains open. The binary reduction is based on support intersections and does not survive signed cancellation: a real factorization can represent a zero entry by cancellation among many nonzero products, so the arbitrary-real question requires a different invariant. The comparison made here is deliberately versioned and contract-specific. We give a self-contained proof of the arbitrary-real matrix-factorization lower bound stated as open in Arkhipov–Kalinin v1, under (1.2)–(1.3) exactly as printed there. One general step of the proof is classical and is cited rather than claimed; see Remark B.1 and Section 4.3. 1.1

Results

The main theorem gives the same exponent without sign, sparsity, or squareness restrictions and with arbitrary finite inner dimension. Theorem 1.1 (Arbitrary-real prefix-factorization order). There are absolute constants 0 < c ≤ C < ∞ such that, for every n ≥ 1, c(log(n + 1))3/2 ≤ cF (Tn ) ≤ c2 (Tn ) ≤ C(log(n + 1))3/2 . (1.4) For a differential-privacy reader the operative consequence is the following, proved as Corollary D.3. Corollary 1.2 (Optimized squared-error order, restated as Corollary D.3). For every ε > 0, within the pure-ε-DP Laplace matrix-mechanism class and over arbitrary finite real factors,  3  log (n + 1) inf MaxSE(ML,R , n) = Θ , Tn =LR ε2 (1.5)  3  log (n + 1) inf MeanSE(ML,R , n) = Θ . Tn =LR ε2 The lower bound is mediated by a finite p-nuclear power. For A ∈ Rm×n and 0 < p < 1, set np (A) =

Pinf A= rq=1 uq vqT

r X

p ∥uq ∥2 ∥vq ∥1 ,

(1.6)

q=1

where the representation is finite and exact. Appendix B records a quantitative finite-dimensional form of the classical approximation-space conversion, with an explicit constant, that lower-bounds np (A) by the complete profile of aggregate column widths. Specializing it to Tn yields a phase transition at p = 2/3. Theorem 1.3 (Fixed-p prefix phase diagram; restated and proved as Theorem D.2). For every fixed 0 < p < 1,   0 < p < 2/3, n, . np (Tn ) = Θp  n log(n + 1), p = 2/3, (1.7)  3p/2 n , 2/3 < p < 1. The subscript in Θp is not decorative: the implied constants are not uniform in p. The sums producing the three orders in (1.7) carry a factor of order |1 − 3p/2|−1 and so blow up as p → 2/3 from either side, and the admissible constant Cp = 3/(1 − 2−(1−p) ) of Theorem B.4 diverges as p → 1. Only p → 0 is benign, where Cp → 6. At the critical value p = 2/3, Hölder’s inequality converts the Ω(n log n) nuclear power into ∥L∥F √ ∥R∥1→1 = Ω((log n)3/2 ) n for every real factorization Tn = LR. Since the normalized Frobenius row energy is no larger than the maximum row energy, the same lower bound applies to c2 . 1.2

The baseline that (1.4) improves on

It is worth recording what part of (1.4) is already classical, so that the increment is visible. For every matrix C one has ∥C∥1→2 ≤ ∥C∥1→1 , since ∥c∥2 ≤ ∥c∥1 columnwise. Hence every pair (L, R) admissible in (1.2)–(1.3) is admissible, at a no-larger product, for the Euclidean-sensitivity costs [2, eq. (48)] γ2 (M ) = inf ∥L∥2→∞ ∥R∥1→2 ,

γF (M ) = inf

M =LR

M =LR

2

∥L∥F √ ∥R∥1→2 , n

(1.8)

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

so that γ2 (Tn ) ≤ c2 (Tn ), γF (Tn ) ≤ cF (Tn ). (1.9) Both γ-quantities for Tn are known at order log n, with the leading constant [10, 12, 11]. Thus (1.9) directly gives cF (Tn ), c2 (Tn ) = Ω(log(n + 1)). A distinct lower-bound route applies beyond matrix mechanisms: Theorem 4 of Henzinger, Upadhyay and Upadhyay [12] covers ε > 0 and 0 ≤ δ < c/(2eε ) for an absolute c > 0. In particular, its pure-DP specialization δ = 0, with 0 < ε ≤ 1, gives MeanSE = Ω(ε−2 log2 n) for every continual counting mechanism; MaxSE ≥ MeanSE gives the same lower order for the maximum-coordinate criterion. These two routes are consistent, but they are not equivalent. So the Ω(log n) part of (1.4) √ is not at issue and is not claimed here. What Theorem 1.1 contributes over that baseline is exactly the additional factor log n, and (1.9) localizes where it comes from: the mixed-norm gap between ∥R∥1→1 and ∥R∥1→2 . Remark 1.4 (Every normalized matrix norm is capped at log n). The Ω(log n) ceiling in (1.9) is not an artifact of the two particular quantities γ2 , γF . Arkhipov and Kalinin [2, Theorem 5.4] prove that every matrix norm γ normalized by γ(stT ) = 1 for all s, t ∈ {−1, 1}n satisfies γ(Tn ) ≤ ⌈log2 n⌉ + 1. Any such norm used as a lower-bound proxy for (1.2)–(1.3) is therefore capped at order log n and cannot witness the exponent 3/2. Consistently, the same authors show that cF and c2 are themselves not norms: both fail the triangle inequality [2, §5]. The lower bound proved below accordingly runs through a quasi-normed scale — the p-nuclear powers (1.6) at√p = 2/3 < 1 — on which no such normalization is available, and the harmonic divergence responsible for the extra log n occurs only because p < 1. 1.3

Proof architecture

The lower bound has three steps and the upper bound one. First, a k-dimensional subspace cannot be close to more than half of the nested suffix indicators: otherwise well-separated close endpoints would produce 2k disjoint long interval vectors close to the same k-plane, contradicting Bessel’s inequality. This gives Dk (Tn ) ≳ n3/2 k −1/2 in the low-rank range 1 ≤ k ≤ n/16 (Appendix A). Second, the classical approximation-space conversion turns p-summable rank-one coefficients into a weighted nuclear-norm approximation profile, and for maps ℓn∞ → ℓm 2 those approximation numbers are exactly the widths Dk (A); a direct proof is retained for its explicit constant, removing the k largest atoms to leave mass at least Dk (A) and accumulating the tails by a reverse Hardy inequality (Appendix B). Third, at p = 2/3 every rank scale contributes order n, producing the harmonic factor, and Hölder’s inequality transfers the critical p-nuclear bound to both costs (Appendix C). A Fenwick interval factorization then supplies matching upper bounds for both costs and for the whole fixed-p phase diagram (Appendix D). 1.4

Why these criteria and this class

Arkhipov and Kalinin record that under pure DP the strongest lower bounds known for both mean and maximum squared error are of order Ω(ε−2 log2 n), against an O(ε−2 log3 n) upper bound, so that the asymptotic gap was open in both; and that “the lack of asymptotically better mechanisms has motivated the view that the current upper bound may be optimal” [2, §1], a view they attribute to [1]. Corollary 1.2 closes that gap inside the pure-ε-DP matrix-mechanism class, and closes it in the direction that view anticipated. The two criteria are the ones this class itself produces. Proposition 3.5 shows that a fixed factorization determines exactly (3.6) and (3.7), and the mean criterion is the one Bairaktari and Larsen identify as the relevant measure for learning applications, reserving ℓ∞ for monitoring tasks [3, §1]. They are also the two smaller quantities: writing e = M(x) − Tn x,   MeanSE ≤ MaxSE ≤ sup E max e2i , x

i

so at a fixed order a lower bound on either of the first two is the stronger statement. The class, in turn, is where the quantitative work on this problem is done: the leading-constant program of [10, 11, 1, 2] lies entirely inside it, and (1.2)–(1.3) are defined only there. The restriction to that class is real, and this framing does not conceal it. Under pure DP the expected-ℓ∞ question √ remains open by a log n factor over all mechanisms, between Ω(ε−1 log3/2 n) and O(ε−1 log2 n) [3, Table 1], whereas (3.6)–(3.7) are determined here on both sides. Part of why the second question closes and the first does not is that the second is asked of a smaller class of mechanisms. 1.5

Claim boundary

Theorem 1.1 is a result about the two costs in (1.2)–(1.3). It is not a lower bound for every continual-release mechanism. It does not replace ∥R∥1→1 by an approximate-DP sensitivity norm, and it says nothing about learning accuracy, utility,

3

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

or any dataset. The qualitative content of the generic width inequality is classical and is attributed in Remark B.1; only its explicit constant and the direct finite-dimensional proof are refinements here. The matrix Tn itself is classical, and is named as such in Section 2. No broader historical priority claim is made for the prefix-width estimate, the fixed-p phase diagram, or the two factorization-cost bounds; the residual limits are recorded in Section 4.

2

Related work and positioning

Continual counting under pure differential privacy. The continual observation model, and with it the binary-tree mechanism for counting, is due to Dwork, Naor, Pitassi and Rothblum [7] and, independently, Chan, Shi and Song [4]. Both obtain O(ε−2 log3 n) squared error. In the versioned line of work compared here, that order remains the upper benchmark and subsequent improvements optimize constants. Before the general factorization of Arkhipov and Kalinin, the strongest leading constant among tree mechanisms was achieved by the k-ary construction with the subtraction trick of Andersson, Pagh, Steiner and Torkamani [1]. Arkhipov and Kalinin [2] improve those leading constants with a general matrix factorization: they define the costs cF and c2 in (1.2)–(1.3), derive the Laplace-mechanism error formulas reproduced in Proposition 3.5, and lift a numerically optimized low-dimensional factorization to all n by an explicit recursion. The upper proof in the present paper uses a classical Fenwick factorization rather than their optimized stacking construction; its role here is to make the order comparison and the p-nuclear upper bound self-contained, not to compete on constants. Lower bounds. Building on the general factorization lower-bound framework of Edmonds, Nikolov and Ullman [8], Henzinger, Upadhyay and Upadhyay [12, Theorem 4] prove a mean-squared-error lower bound for every (ε, δ)differentially private continual counting mechanism when ε > 0 and 0 ≤ δ < c/(2eε ) for an absolute c > 0. At δ = 0 and 0 < ε ≤ 1, it is Ω(ε−2 log2 n); the inequality MaxSE ≥ MeanSE transfers that order to the maximumcoordinate criterion. The resulting logarithmic gap to the O(ε−2 log3 n) pure-DP upper bound remains open for general mechanisms under the versioned comparison in [2]. Within the matrix-mechanism class, Arkhipov and Kalinin [2] prove an Ω(ε−2 log3 n) lower bound for factorizations whose factors have entries in {0, 1} — a class containing the binary tree mechanism and the k-ary tree mechanisms without the subtraction trick — via a skew-Bollobás set-system argument, and state the extension to arbitrary factorizations as open. Two further observations of theirs bound that binary class from inside it. Their 0/1 lower bound for MaxSE carries leading constant 0.168, larger than the constant 0.0778 achieved by their own general factorization, so improving even the leading constant requires leaving the binary class; and their Theorem 5.4 caps every normalized matrix norm on Tn at order log n (Remark 1.4), which closes the convex route to the exponent rather than merely leaving it unexplored. Under their contract, Theorem 1.1 proves the corresponding order for arbitrary real factors; it says nothing about the second half of their open problem, which asks for a lower bound beyond the matrix mechanism altogether. Concurrently with [2], Bairaktari and Larsen [3, Theorem 1] prove that every (ε, δ)-differentially private continual counting mechanism has !   log3/2 n max E ∥M(x) − Tn x∥∞ = Ω max{ε, δ} x∈{0,1}n for n−1+Ω(1) < ε < 1 and 0 < δ < C with C > 0 an absolute constant. Since a pure ε-DP mechanism is (ε, δ)-DP for every δ > 0, taking δ below min{C, ε} gives Ω(ε−1 log3/2 n) for pure DP as well, as those authors record; the bound holds for every mechanism and not only for matrix mechanisms. It does not subsume Theorem 1.1, and the reason is the error functional rather than the mechanism class: their quantity takes the expectation after maximizing across coordinates, whereas (3.6) and (3.7) average squared coordinate errors. These functionals are not ordered in general, so a lower bound on the former does not transfer to either squared-error criterion. The gap is genuine and not merely an artifact of proof technique. For n independent standard coordinates, E[maxi |ei |]2 is of order log n while maxi E[e2i ] is of order 1. In the other direction, already in one dimension an error equal to L with probability L−2 and zero otherwise has squared expected absolute error L−2 but mean squared error 1. The same non-transfer is recorded by [2, §1.2], and Remark 3.7 states the corresponding boundary here. The two results are complementary: theirs reaches beyond matrix mechanisms under an expected-maximum criterion, while Theorem 1.1 determines the arbitrary-real factorization costs that govern the coordinatewise and mean squared errors. Approximate-DP factorization norms. Replacing ℓ1 by ℓ2 sensitivity turns cF , c2 into the matrix norms γF , γ2 of (1.8). For the counting matrix these are settled. Mathias’s classical circulant estimate supplies the longstanding upper bound for γ2 (Tn ) [18]; Fichtenberger, Henzinger and Upadhyay [10] compute the leading term with its constant through completely bounded norms, Henzinger, Upadhyay and Upadhyay [12] give a matching singular-value lower bound for γF , and Henzinger, Kalinin and Upadhyay [11] sharpen the next term. The general theory of these norms is

4

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

developed by Matoušek, Nikolov and Talwar [17]. Denisov et al. [6] also optimize matrix factorizations for adaptive streams and private stochastic optimization; their setting uses approximate-DP Euclidean sensitivity and is distinct from the pure-Laplace objectives here. Those results do not settle (1.2)–(1.3): by (1.9) they give only the Ω(log n) baseline, and the mixed-norm gap they discard is precisely what contributes the additional square-root logarithm. The prefix matrix in Banach space geometry. The matrix (1.1) is not specific to differential privacy. It is the coefficient matrix of the finite summation operator Σn ∈ L(ℓn1 , ℓn∞ ) of Pietsch and Wenzel [20, §0.7.3], one of the standard test operators of that field: their §7.6 uses it to characterise super weak compactness and superreflexivity. The two are the same array of scalars but not the same normed-space operator: the p-nuclear functional (1.6) used below treats Tn as an operator ℓn∞ → ℓn2 instead, and that realization is what fixes the atom weight ∥uq ∥2 ∥vq ∥1 . Their summary table records twelve quantities for Σn : ten resolved asymptotic entries and two open rows. Every entry is an ideal norm relative to an orthonormal system; none is a nuclear quantity, an approximation number, a width, or a factorization cost, and the question asked there — whether the Σn factor through one fixed operator with uniformly bounded factor norms, pursued further by Wenzel [22] — is a different one from the growth rate measured here. This is positioning, not priority: the object is classical, while none of the quantities catalogued in the monograph is the nuclear-side functional studied below. Approximation spaces and p-nuclearity. Pietsch [19] introduced approximation schemes, their approximation numbers, the spaces obtained by weighting those numbers, and the Transformation Theorem that maps one such space into another when sparse objects are sent to rank-controlled objects. Hinrichs and Pietsch [13] develop the theory of p-nuclear operators in Grothendieck’s sense and, in their §7, apply that apparatus with the nuclear operators as ambient space and the finite-rank operators as approximating sets; their Theorem 7.1 is the inclusion this paper needs, and Remark B.1 records the specialization and the parameter transfer. Neither source states the prefix-width estimate, the fixed-p evaluation for Tn , or the two factorization-cost bounds: their worked examples are identity maps and Fourier matrices. Of the surrounding literature, Kwapień and Pełczyński [14] prove logarithmic bounds for the main triangle projection on unconditional matrix norms — Banach-norm statements, whereas convexifying (1.2)–(1.3) would discard the nonconvex scale responsible for the exponent 3/2, a loss that Remark 1.4 records as a barrier proved in the source compared here rather than as a stylistic preference; Laprestè [15] and Reinov [21] supply classical language for mixed ℓ2 /ℓ1 factorizations and finite tensor quasi-norms; and Fewster, Ojima and Porrmann [9] use the countable Grothendieck convention that Proposition 3.9 reconciles with the finite one.

3

Preliminaries

Throughout, log denotes the natural logarithm. PThe asymptotic statements are unaffected by the base, but the explicit constants are not: the harmonic comparison k≤m k −1 ≥ log(m + 1) used in the proof of Theorem C.1 holds for the natural logarithm and fails in base 2. The one place where a binary logarithm appears, in the statement of [2, Theorem 5.4] quoted in Remark 1.4, is written log2 explicitly. 3.1

Norms and factorization costs

For a real matrix M , write ∥M ∥2→∞ = max∥Mi,· ∥2 ,

∥M ∥1→1 = max∥M·,j ∥1 .

i

j

(3.1)

The former is the largest Euclidean row norm, and the latter the largest ℓ1 column norm. The inequality ∥L∥F √ ≤ ∥L∥2→∞ n

(3.2)

implies cF (Tn ) ≤ c2 (Tn ). 3.2

Differential privacy and the factorization mechanism

Definition 3.1 (Adjacency and pure differential privacy). Streams x, x′ ∈ Rn are adjacent, written x ∼ x′ , when ∥x − x′ ∥1 ≤ 1. For ε > 0, a randomized mechanism M with values in Rn is ε-differentially private if Pr[M(x) ∈ S] ≤ eε Pr[M(x′ ) ∈ S] for every pair x ∼ x′ and every measurable S ⊆ Rn .

5

(3.3)

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

Lemma 3.2 (ℓ1 sensitivity of a factor). For every R ∈ Rr×n , sup ∥Rd∥1 = ∥R∥1→1 .

(3.4)

∥d∥1 ≤1

Proof. Writing R·,j for the j-th column, ∥Rd∥1 =

n X

dj R·,j

j=1

≤ 1

n X

|dj | ∥R·,j ∥1 ≤ ∥d∥1 ∥R∥1→1 ,

j=1

which gives ≤. Equality holds at d = ej ∗ for any column j ∗ attaining the maximum in (3.1). For a factorization Tn = LR with R ∈ Rr×n , define the additive Laplace matrix mechanism ML,R (x) = L(Rx + Z),

(3.5)

r

where the coordinates of Z ∈ R are independent centered Laplace variables of scale b = ∥R∥1→1 /ε. Since LR = Tn ̸= 0 we have R ̸= 0, so b > 0. Proposition 3.3 (The factorization mechanism is ε-DP). For every ε > 0 and every factorization Tn = LR, the mechanism (3.5) is ε-differentially private in the sense of Definition 3.1. Let x ∼ x′ and put d = x − x′ , so ∥d∥1 ≤ 1. The random vector Rx + Z has density w 7→ Proof. Q r −r r ′ (2b) i=1 exp(−|wi − (Rx)i |/b) on R , so for every w the ratio of the densities at x and at x is at most     ∥Rx − Rx′ ∥1 ∥R∥1→1 ∥d∥1 exp ≤ exp ≤ eε , b b using the triangle inequality, Lemma 3.2 and the choice of b. Integrating over any measurable set shows that x 7→ Rx+Z satisfies (3.3); this is the Laplace mechanism [5] applied at sensitivity ∥R∥1→1 . The map w 7→ Lw is fixed and does not depend on the stream, so composing with it preserves the guarantee. 3.3

Fixed-factorization and optimized errors

For any randomized release M, write h
2 i MaxSE(M, n) = sup max E M(x)i − (Tn x)i , x 1≤i≤n

MeanSE(M, n) = sup x

 1  E ∥M(x) − Tn x∥22 . n

(3.6) (3.7)

The suprema are over the stream domain of the mechanism, which by Definition 3.1 is Rn here; a supremum rather than a maximum is used because on an unbounded domain a general mechanism need not attain one. For the additive mechanism in (3.5) the error distribution does not depend on x, so both suprema are attained and equal the constant value. Remark 3.4 (Stream domain relative to the compared contract). Arkhipov and Kalinin state continual counting on binary streams x ∈ {0, 1}n , with the same unit ℓ1 adjacency [2, §1.1]. Definition 3.1 uses the ambient formulation x ∈ Rn instead, which enlarges the adjacency relation and therefore imposes the stronger privacy requirement. Neither the algebraic costs nor the errors change. By Lemma 3.2, ∥R∥1→1 is the largest ℓ1 column norm and is already attained at d = ±ej — exactly the differences of adjacent binary streams — so the calibrated noise scale in (3.5) is the same under either domain, and by the previous paragraph so are (3.6)–(3.7). The factorization problem is therefore identical, and the lower bounds proved below are statements about (1.2)–(1.3) alone, in which no stream domain appears. Proposition 3.5 (Exact squared-error formulas). For ε > 0 and a fixed factorization Tn = LR, 2 MaxSE(ML,R , n) = 2 ∥L∥22→∞ ∥R∥21→1 , (3.8) ε 2 (3.9) MeanSE(ML,R , n) = 2 ∥L∥2F ∥R∥21→1 . nε Consequently, the infima of the two errors over all finite real factorizations are 2c2 (Tn )2 ε2

and

respectively.

6

2cF (Tn )2 , ε2

(3.10)

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

Proof. The additive error is LZ. A centered Laplace variable of scale b has variance 2b2 . Independence and zero means therefore give, for row i of L, 2∥R∥21→1 ∥Li,· ∥22 . E[(LZ)2i ] = ε2 Maximizing over i gives (3.8); averaging over the n rows gives (3.9). Taking the corresponding infima and using (1.2)–(1.3) proves (3.10). Remark 3.6 (The two optimized errors need not be equal). Equation (3.10) identifies two separate infima; their common asymptotic√order does not make p their finite values equal. For the two-step prefix matrix, Arkhipov and Kalinin prove c2 (T2 ) = 2 and cF (T2 ) = 3/2 [2, Lemmas 5.2–5.3]. Hence 4 3 inf MaxSE(ML,R , 2) = 2 , inf MeanSE(ML,R , 2) = 2 . T2 =LR T2 =LR ε ε Corollaries 1.2 and D.3 assert only that the two sequences have the same order as n grows. Remark 3.7 (What these errors do not measure). The quantity in (3.8) is maxi E[(LZ)2i ]. It is not E[maxi (LZ)2i ], nor does it determine E[maxi |(LZ)i |]. The coordinates of LZ are generally correlated, and bounds for either expected maximum require a separate probabilistic argument. The last quantity is the criterion of [3]; the two directions are compared in Section 2. 3.4

p-nuclear power

Definition 3.8 (Finite p-nuclear power). For A ∈ Rm×n and 0 < p < 1, define r X λpq , λq = ∥uq ∥2 ∥vq ∥1 , np (A) = Pinf r A=

T q=1 uq vq q=1

(3.11)

where r < ∞. The vectors uq ∈ Rm and vq ∈ Rn define rank-one operators from ℓn∞ to ℓm 2 , and λq is the corresponding operator-norm product. The countable convention is Grothendieck’s, in the form stated by Hinrichs and Pietsch [13, eq. (1.3)]: for 0 < p ≤ 1, an operator T : X → Y between Banach spaces is p-nuclear when it admits a representation X Tx = τk ⟨x, x∗k ⟩yk , (x∗k ) ⊂ BX ∗ , (yk ) ⊂ BY , (τk ) ∈ ℓp , (3.12) k≥1

and one sets νp (T ) = inf∥(τk )∥ℓp over all such representations. Taking X = ℓn∞ , so that BX ∗ is the ℓ1 ball, and T p Y = ℓm 2 , a rank-one atom uq vq normalizes in both directions to τq = ∥uq ∥2 ∥vq ∥1 = λq . So νp (A) is exactly the infimum in (3.11) taken over countable representations. The next proposition says that the restriction to finite ones costs nothing. Proposition 3.9 (Finite and countable conventions agree). For every finite real matrix A and every 0 < p < 1, np (A) = νp (A)p , (3.13) n m where νp is the Grothendieck quasi-norm of (3.12) for operators ℓ∞ → ℓ2 . Proof. Every finite representation is countable, giving one inequality. Conversely, consider a countable representation X X A= uq vqT , λpq < ∞. (3.14) q≥1

q≥1

Because 0 < p < 1, the latter summability implies q λq < ∞: after finitely many terms, λq ≤ 1 and hence λq ≤ λpq . Thus the partial sums converge to A in the operator norm ℓn∞ → ℓm 2 . P

Let BN be the residual after N terms. Its finite column decomposition is n X BN = (BN ej )eT j.

(3.15)

j=1

The additional p-cost is bounded by n X

∥BN ej ∥p2 ≤ n∥BN ∥pℓn →ℓm −→ 0. ∞

2

(3.16)

j=1

Appending (3.15) to the initial N atoms yields a finite exact representation with asymptotically no extra cost. Taking infima proves the reverse inequality.

7

Arbitrary Real Factorization Costs for Continual Counting

3.5

A P REPRINT

Aggregate column widths

Definition 3.10 (Aggregate column width). For A ∈ Rm×n , with columns aj = Aej , define Dk (A) =

n X

infm

E⊆R dim E≤k j=1

dist(aj , E)2 .

(3.17)

Throughout, E ranges over linear subspaces of Rm and dist(a, E)2 = inf ∥a − e∥2 e∈E

(3.18)

is the Euclidean distance from a to E; the subscript records which norm measures the distance, not a coordinate. Unlike a spectral approximation number, Dk (A) sums Euclidean distances column by column. This mixed aggregate geometry matches the ℓ1 coefficient norm in (3.11).

4

Interpretation and limitations

4.1

What the exponent boundary says

Theorem 1.1 rules out an exponent improvement obtained solely by allowing signed, dense, rectangular factors of arbitrary inner dimension. What replaces the support-intersection step available for binary factors is that the prefixspecific input measures all low-rank aggregate widths simultaneously, and that cancellation stays inside an exact signed residual until a norm is applied. The critical value p = 2/3 is forced by the interaction of three scales: in the low-rank range 1 ≤ k ≤ n/16, Dk (Tn ) ≍ n3/2 k −1/2 ,

k −p Dk (Tn )p ≍ n3p/2 k −3p/2 ,

and the series becomes harmonic exactly when 3p/2 = 1. That range is the one Lemmas A.1–A.2 establish and the only one the proof uses; the two-sided estimate does not extend to all k ≤ n, since the columns of Tn are linearly independent and hence Dn (Tn ) = 0. Hölder then converts the 2/3-power into a 3/2 exponent for the factorization cost. 4.2

Mechanism and privacy scope

The result concerns the factorization class in (3.5). It does not prove a lower bound for every interactive or non-matrix continual mechanism, and it therefore leaves untouched the second half of the open problem of [2]. It is also specific to pure ε-differential privacy through the ℓ1 sensitivity ∥R∥1→1 of Lemma 3.2; approximate-DP mechanisms governed by ℓ2 sensitivity have a different factorization geometry, and their order for Tn is log n rather than log3/2 n [10, 12]. Corollary D.3 concerns the maximum of coordinatewise expected squared error and the mean expected squared error. By Remark 3.7, it does not determine an expected maximum across coordinates; that criterion is the one bounded by [3], whose result is neither implied by nor implies Theorem 1.1. No empirical or learning-theoretic conclusion follows from these matrix costs. 4.3

Attribution

The conversion from p-summable rank-one coefficients to a weighted nuclear-norm approximation profile belongs to the approximation-space theory of the Jena school. It is a finite-dimensional specialization of Pietsch’s Transformation Theorem [19], and Theorem 7.1 of Hinrichs and Pietsch [13] states the corresponding operator-ideal inclusion directly; Remark B.1 records both reductions with their parameter transfers. Theorem B.4 contributes the explicit constant Cp and a self-contained finite-dimensional proof, nothing more. The matrix Tn is likewise classical: it is the coefficient matrix of the finite summation operator Σn : ℓn1 → ℓn∞ of Pietsch and Wenzel [20, §0.7.3], read here instead as an operator ℓn∞ → ℓn2 . The prefix-dependent steps proved in this paper are the width estimate of Lemma A.1, its evaluation at every fixed p in Theorem D.2, and the transfer to cF and c2 in Theorem C.2. This describes the proof decomposition, not a claim that the statements are absent from all earlier literature. The comparison with [2] is versioned and contract-specific: that source states the arbitrary-factor lower bound as open, and Theorem 1.1 supplies it under the same two cost definitions.

8

Arbitrary Real Factorization Costs for Continual Counting

5

A P REPRINT

Conclusion

For the prefix workload, arbitrary signed real factorizations have the same (log(n + 1))3/2 asymptotic cost as the known upper constructions, under both the normalized Frobenius and the maximum-row objective. For ε > 0, within the finite-dimensional pure-ε-DP Laplace matrix-mechanism class the resulting optimized maximum and mean squared errors have order Θ(ε−2 log3 (n + 1)). Relative to the exact contract stated as open in Arkhipov–Kalinin v1, the matrix lower bound covers arbitrary signed, dense, rectangular factors of arbitrary finite inner dimension and, as a cost inequality only, countable inner dimension by Remark C.4. The proof combines a prefix-specific aggregate-width estimate with a classical approximation-space engine: the transformation theorem of Pietsch, or the corresponding operator-ideal inclusion of Hinrichs and Pietsch, supplies the generic conversion from p-summable atomic coefficients to a weighted nuclear-norm approximation profile, and the direct tail and reverse-Hardy argument included here supplies an explicit constant. At the critical exponent 2/3, the prefix profile produces a harmonic lower bound, and Hölder transfers it to factorization energy. The same analysis yields matching fixed-p asymptotics for the finite prefix operator, together with a self-contained Fenwick upper construction. Extending the lower bound beyond matrix mechanisms, closing the remaining log n gap between Ω(ε−2 log2 n) for general pure-DP continual counting and Θ(ε−2 log3 n) for the matrix class, and sharpening the constants are separate questions.

9

Arbitrary Real Factorization Costs for Continual Counting

A

A P REPRINT

Aggregate width of the prefix chain

Write tj = Tn ej . Thus tj is the indicator of the suffix {j, . . . , n}. Lemma A.1 (Dense endpoints force aggregate width). If n ≥ 16 and 1 ≤ k ≤ n/16, then Dk (Tn ) ≥

1 n3/2 √ √ . 16 2 k

(A.1)

Proof. Fix a subspace E with dim E ≤ k and a threshold θ > 0. Suppose that at least n/2 indices satisfy dist(tj , E)2 < θ.

(A.2)

List any G ≥ n/2 such indices as g1 < · · · < gG . Set M = 2k and



 G s= . 4k

(A.3)

Since k ≤ n/16 and G ≥ n/2, one has G/(4k) ≥ 2, so s≥

G n ≥ ≥ 1. 8k 16k

(A.4)

For 0 ≤ ℓ < M , choose σℓ = g2ℓs+1 , τℓ = g(2ℓ+1)s+1 . All requested indices are available: since 2M s = 4ks ≤ G and s ≥ 1,

(A.5)

(2M − 1)s + 1 ≤ G − s + 1 ≤ G. The intervals Iℓ = [σℓ , τℓ ) are pairwise disjoint and have cardinality at least s. Moreover, xℓ = tσℓ − tτℓ = 1Iℓ .

(A.6)

Hence the normalized vectors

xℓ , 0 ≤ ℓ < M, ∥xℓ ∥2 are orthonormal. If PE denotes orthogonal projection onto E, Bessel’s inequality gives yℓ =

M −1 X

dist(yℓ , E)22 = M −

ℓ=0

M −1 X

∥PE yℓ ∥22 ≥ M − k = k.

(A.7)

ℓ=0

Distance to a linear subspace is a seminorm. Both endpoints in (A.5) satisfy (A.2), so

Since ∥xℓ ∥2 ≥

√

dist(xℓ , E)2 ≤ dist(tσℓ , E)2 + dist(tτℓ , E)2 < 2θ.

(A.8)

s, equations (A.7)–(A.8) imply k<M

4θ2 8kθ2 = . s s

Choose

r θ=

(A.9)

n . 128k

By (A.4), θ2 ≤ s/8, contradicting (A.9). Therefore at least n/2 columns have distance at least their distances gives r n X 1 n3/2 n n dist(tj , E)2 ≥ = √ √ . 2 128k 16 2 k j=1 Taking the infimum over E proves the lemma.

10

p

n/(128k). Summing

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

Lemma A.2 (Matching aggregate-width upper order). For 1 ≤ k ≤ n, Dk (Tn ) ≤

√ n3/2 2 √ . k

(A.10)

Consequently,  3/2  n Dk (Tn ) = Θ √ k uniformly for n ≥ 16 and 1 ≤ k ≤ n/16. Proof. Partition {1, . . . , n} into k consecutive nonempty blocks, each of size at most ⌈n/k⌉, and let E be the span of their indicator vectors. Each suffix indicator tj agrees outside the block containing j with the indicator of a union of complete blocks. The latter vector lies in E. Therefore r p 2n dist(tj , E)2 ≤ ⌈n/k⌉ ≤ . k Summing over the n columns proves (A.10). The matching lower order follows from Lemma A.1. P Remark A.3 (Why a quadratic shortcut is insufficient). A lower bound on j dist(tj , E)22 does not imply the required P lower bound on j dist(tj , E)2 by reversing Cauchy–Schwarz. The false inequality v u X n X u n 2 dj ≥ tn dj j=1

j=1

already fails for (d1 , . . . , dn ) = (1, 0, . . . , 0) when n > 1. Lemma A.1 instead proves that a fixed positive fraction of the columns is far from every k-plane.

B

From widths to a p-nuclear obstruction

B.1

The widths are approximation numbers in the nuclear norm

Let N(ℓn∞ , ℓm 2 ) denote the finite-dimensional space of nuclear operators equipped with its nuclear norm ν1 . For C : ℓn∞ → ℓm 2 , n X ν1 (C) = ∥Cej ∥2 . (B.1) j=1 T j (Cej )ej gives the upper bound; conversely, every nuclear representation

P

Indeed, the column representation C = P C = q yq wqT satisfies X X X X ∥Cej ∥2 ≤ ∥yq ∥2 |wq (j)| = ∥yq ∥2 ∥wq ∥1 , j

q

j

q

and taking the infimum gives the reverse bound. Here ν1 is the ordinary nuclear norm; it is distinct from the p-nuclear quasi-norm νp of (3.12). Let aj (A | N) be the j-th approximation number of A when the ambient norm is ν1 and the approximating set consists of operators of rank at most j − 1. Equation (B.1) gives the exact identification ak+1 (A | N) =

inf rank(B)≤k

ν1 (A − B) = Dk (A).

(B.2)

For one inequality direction, take E = range(B) and sum the columnwise distance bounds. For the other, take B = PE A, where PE is the orthogonal projection onto a k-dimensional approximating subspace, and then take the infimum over E. Remark B.1 (The conversion below is classical). Theorem B.4 is a finite-dimensional, quantitative form of an inclusion between operator ideals that is not due to this paper, and the attribution is recorded here rather than in a numbered result of our own. In the terminology of Hinrichs and Pietsch [13, §7], take the approximation scheme whose ambient space is the nuclear operators N(X, Y ) under the nuclear norm and whose approximating sets are the operators of rank at most j, and

11

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

1/s

ϱ ϱ−1/w write Napp aj (x | X)) | ℓw ∥. s,w := (N)w for the resulting approximation space, with quasi-norm ∥x | Xw ∥ = ∥(j Their Theorem 7.1 states

Nr,w ⊆ Napp s,w

1 1 s = r − 1,

if 0 < r < 1,

0 < w ≤ ∞.

(B.3)

Take r = w = p, so that Np,p = Np in that paper’s abbreviation and ϱ = 1/s = 1/p − 1. The target quasi-norm of A is then X 1/p p 1/p X −p A | Napp = j (1/p−1)−1/p aj (A | N) = j aj (A | N)p , s,p j≥1

j≥1

with the ambient norm and approximating class exactly those of (B.2), so aj (A | N) = Dj−1 (A). Since (B.3) is a bounded inclusion of quasi-Banach operator ideals, re-indexing by k = j − 1, using k −p ≤ 2p (k + 1)−p , and applying Proposition 3.9 yields (B.14) below with an unspecified constant depending only on p. The same conclusion follows from Pietsch’s earlier framework [19, pp. 117–118, 120, 123–124, 126]: the Transformation Theorem applies with sequence exponent u = p, smoothness ϱ = 1/p − 1 and rank-growth exponent 1, the 1/p−1 sparse-sequence identity on p. 123 supplies (ℓ1 , fm )p = ℓp,p = ℓp , and p. 126 places the nuclear operators in the framework. The short direct proof in Sections B.2–B.3 is retained because it keeps the finite-dimensional chain self-contained, it supplies the explicit admissible constant Cp = 3/(1 − 2−(1−p) ) appearing in the displayed lower bound, and it makes visible that cancellation is retained inside a signed residual until a norm is applied. Its qualitative content is not claimed here; the unspecified constant furnished by the classical route would suffice for every asymptotic consequence in this paper. B.2

Rank-one tails

Lemma B.2 (Every atom tail pays the aggregate width). Let A=

r X

uq vqT ,

λq = ∥uq ∥2 ∥vq ∥1 ,

(B.4)

q=1

and relabel the atoms so that λ1 ≥ · · · ≥ λr ≥ 0. Then, for 0 ≤ k < r, X λq ≥ Dk (A).

(B.5)

q>k

Proof. Let Ek = span{u1 , . . . , uk }, so dim Ek ≤ k. For column j, the contribution of the initial k atoms lies in Ek . Forming the exact signed residual before applying a norm gives Dk (A) ≤

n X X j=1

≤

X q>k

uq vq (j)

q>k

2

∥uq ∥2

n X

|vq (j)| =

j=1

X

λq .

(B.6)

q>k

No sign restriction is used. B.3

Reverse Hardy accumulation

Lemma B.3 (Tail Hardy inequality below one). For every 0 < p < 1, every finite nonincreasing sequence λ1 ≥ · · · ≥ λr ≥ 0 satisfies  p r−1 r X X X 3 k −p  λq  ≤ Cp λpq , Cp = . (B.7) −(1−p) 1−2 q=1 k=1 q>k Proof. Group k into dyadic blocks 2s ≤ k < 2s+1 , and define X Bs = λq , bt = q≥2s

X 2t ≤q<2t+1

12

λq ,

(B.8)

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

with all sums truncated at r. Since 0 < p < 1, p

 Bsp = 

X

bt  ≤

t≥s

X p bt .

(B.9)

t≥s

Also, X

k −p ≤ 2s(1−p) .

(B.10)

2s ≤k<2s+1

For k in the s-th block,

P

q>k λq ≤ Bs . Therefore r−1 X

p

 k −p 

k=1

X

λq  ≤

X

2s(1−p) Bsp

s

q>k

X pX ≤ bt 2s(1−p) t

≤ Monotonicity gives bt ≤ 2t λ2t , hence

s≤t

1

X

1 − 2−(1−p)

2t(1−p) bpt .

2t(1−p) bpt ≤ 2t λp2t .

For t ≥ 1, the preceding dyadic block contains 2

t−1

(B.11)

t

(B.12)

terms, each at least λ2t , so

2t λp2t ≤ 2

t 2X −1

λpq .

(B.13)

q=2t−1

The preceding blocks are disjoint, while the t = 0 term contributes λp1 . Substituting (B.13) into (B.11) proves (B.7). Theorem B.4 (Explicit finite-dimensional width obstruction). For every finite real matrix A and 0 < p < 1, np (A) ≥

1 Cp

rank(A)−1

X

k −p Dk (A)p ,

(B.14)

k=1

where Cp = 3/(1 − 2−(1−p) ) is admissible. The sum is empty when rank(A) ≤ 1. Proof. If rank(A) ≤ 1, the right side is zero and the claim is immediate. Assume rank(A) ≥ 2. Fix a finite rank-one representation, delete zero atoms, and sort the atom costs as in Lemma B.2. If r atoms remain, then r ≥ rank(A). Lemmas B.2 and B.3 give  p r−1 X X X Cp λpq ≥ k −p  λq  q

k=1

q>k

rank(A)−1

≥

X

k −p Dk (A)p .

k=1

The right side is independent of the representation. Taking the infimum proves (B.14).

C

The critical exponent and the factorization lower bound

Theorem C.1 (Critical nuclear lower bound). Let cN =

1 − 2−1/3 . 144

(C.1)

For every n ≥ 1, n2/3 (Tn ) ≥ cN n log(n + 1).

13

(C.2)

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

Proof. We begin with n ≥ 32. Theorem B.4 and Lemma A.1 imply ⌊n/16⌋

X

C2/3 n2/3 (Tn ) ≥

k −2/3 Dk (Tn )2/3

k=1 ⌊n/16⌋ X 1 √ ≥ (16 2)−2/3 n k k=1

⌊n/16⌋

=

n X 1 . 8 k

(C.3)

k=1

√ The equality uses (16 2)2/3 = (29/2 )2/3 = 8. The harmonic bound gives ⌊n/16⌋

 j n k X 1 n + 1 > log . ≥ log k 16 16

k=1

For n ≥ 32, 1 n ≥ log(n + 1). (C.4) 16 6 Indeed, the ratio of the left logarithm to log(n + 1) is increasing on this range and already exceeds 1/6 at n = 32. Combining (C.3)–(C.4) yields n log(n + 1) n2/3 (Tn ) ≥ = cN n log(n + 1). 48C2/3 log

It remains to cover 1 ≤ n < 32. For every rank-one representation, choose a unit entry (i, j) of Tn . Then X X X 1 = |(Tn )ij | ≤ |uq (i)vq (j)| ≤ ∥uq ∥2 ∥vq ∥1 = λq . q

q

(C.5)

q

Subadditivity at exponent 2/3 gives !2/3 1≤

X

≤

λq

q

X

λ2/3 q .

(C.6)

q

Taking the infimum yields n2/3 (Tn ) ≥ 1. Since n log(n + 1) ≤ 31 log 32 < 108 and cN < 1/108, the stated bound follows for the remaining dimensions. Theorem C.2 (Arbitrary-real lower bound). Every finite-dimensional real factorization Tn = LR satisfies ∥L∥F 3/2 √ ∥R∥1→1 ≥ c3/2 . N (log(n + 1)) n

(C.7)

Consequently, 3/2

cF (Tn ), c2 (Tn ) ≥ cN (log(n + 1))3/2 .

(C.8)

Proof. Let β = ∥R∥1→1 . Since LR = Tn ̸= 0, one has β > 0. Replacing (L, R) by (βL, β −1 R) preserves the product and the cost, so assume ∥R∥1→1 = 1. Write lq for column q of L and rqT for row q of R. Then Tn =

X

lq rqT .

(C.9)

q

Furthermore, X q

∥rq ∥1 =

X j,q

14

|Rqj | ≤ n,

(C.10)

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

2/3

because each of the n columns of R has ℓ1 norm at most one. Hölder with exponents 3 and 3/2, applied to aq = ∥lq ∥2 2/3 and bq = ∥rq ∥1 , gives !1/3 !2/3 X X X
2/3 2 ∥lq ∥2 ∥rq ∥1 ≤ ∥lq ∥2 ∥rq ∥1 q

q

q

2/3 ≤ ∥L∥F n2/3 .

(C.11)

The left side is the cost of an admissible rank-one representation. Theorem C.1 therefore gives 2/3

cN n log(n + 1) ≤ ∥L∥F n2/3 . Rearranging yields

3/2 √ n(log(n + 1))3/2 . ∥L∥F ≥ cN Undoing the normalization proves (C.7). Taking the infimum proves the cF lower bound, and (3.2) proves the c2 lower bound.

Remark C.3 (Constants). The constant in Theorem C.2 is explicit but not optimized. Several estimates are deliberately crude. All main conclusions concern asymptotic order rather than a leading constant. Remark C.4 (Countably infinite inner dimension is also covered). The infima (1.2)–(1.3) range over finite inner dimension, matching the contractP of [2]. The proof of Theorem C.2 does not use that restriction. Let Q be countable, L ∈ Rn×Q and R ∈ RQ×n with q∈Q Liq Rqj = (Tn )ij for all i, j. Then (C.10) still holds, because it sums the ℓ1 P norms of the n columns of R whatever the number of rows; q ∥lq ∥22 = ∥L∥2F is unaffected, and the claim is vacuous unless it is finite; Hölder applies to countable sums; and the resulting rank-one representation has finite 2/3-cost, so Proposition 3.9 converts it into a finite one without asymptotic loss. Hence (C.7) holds verbatim for countable inner dimension, and enlarging the infima in (1.2)–(1.3) to countable inner dimension changes neither side of (1.4). This is a statement about the two matrix costs; it does not define a Laplace mechanism with countably many noise coordinates.

D

Dyadic upper bounds and the fixed-p phase

Lemma D.1 (Fenwick interval factorization). There is an absolute constant C < ∞ such that cF (Tn ), c2 (Tn ) ≤ C(log(n + 1))3/2 ,

n2/3 (Tn ) ≤ Cn log(n + 1).

(D.1)

Proof. Let N = 2h be the least power of two with N ≥ n. For 1 ≤ q ≤ N , define ℓq = 2ν2 (q) ,

Iq = {q − ℓq + 1, . . . , q},

ν2 (q)

where ν2 (q) is the largest exponent such that 2

(D.2)

divides q. Let R be the interval–point incidence matrix

Rq,j = 1{j ∈ Iq }. Intervals of a fixed length are disjoint. Each point therefore belongs to at most one interval at each of the h + 1 possible lengths, while point 1 belongs to the intervals indexed by 1, 2, 4, . . . , N . Hence ∥R∥1→1 = h + 1.

(D.3)

Starting from a prefix endpoint q0 = i and repeatedly setting qs+1 = qs − ℓqs partitions {1, . . . , i} into at most h + 1 of the intervals Iq . Let row i of L indicate those intervals. Then LR = TN ,

∥L∥2→∞ ≤

√

h + 1,

√ ∥L∥F √ ≤ h + 1. N

(D.4)

Thus both costs for TN are at most (h + 1)3/2 . For the nuclear estimate, let uq be column q of L and let vqT be row q of R. The interval Iq can occur only in prefix decompositions with endpoint between q and q + ℓq − 1. Therefore p ∥uq ∥2 ≤ ℓq , ∥vq ∥1 = ℓq . (D.5)

15

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

The exact low-bit count is N X

 ℓq = N

1+

q=1

h 2

 .

(D.6)

Indeed, for 0 ≤ s < h, exactly N/2s+1 indices have ℓq = 2s , while q = N contributes ℓN = N . It follows from (D.5) that   N X h n2/3 (TN ) ≤ ℓq = N 1 + . (D.7) 2 q=1 There is one harmless endpoint slack in (D.5). The interval IN = {1, . . . , N } lies entirely inside the matrix. Its formal endpoint-occurrence range N, . . . , N + ℓN − 1 = N, . . . , 2N − 1 extends beyond the available prefixes, so IN occurs only in the decomposition of the N -th prefix. Consequently √ ∥uN ∥2 = 1, rather than ℓN ; the displayed estimate remains a valid upper bound. Finally, restrict L to its initial n rows and R to its initial n columns. Their product is Tn , and no relevant row norm, √ column norm, Frobenius norm, or atom cost increases. Since N < 2n, changing the Frobenius normalization from N √ √ to n costs less than 2. Since h + 1 = O(log(n + 1)), all claims follow. Theorem D.2 (Fixed-p phase diagram; restatement of Theorem 1.3). For every fixed 0 < p < 1,   0 < p < 2/3, n, . np (Tn ) = Θp  n log(n + 1), p = 2/3,  3p/2 n , 2/3 < p < 1.

(D.8)

Proof. For n ≥ 32, Theorem B.4 and Lemma A.1 yield ⌊n/16⌋

np (Tn ) ≳p n3p/2

X

k −3p/2 .

(D.9)

k=1

The sum has order n1−3p/2 , log(n + 1), or 1, according as p < 2/3, p = 2/3, or p > 2/3. This gives the three lower orders. 3/2

For the upper bound, use the Fenwick factorization at N = 2h . By (D.5), atom q has product cost at most ℓq . The low-bit multiplicities give h−1 N X s(3p/2−1) 2 + N 3p/2 . (D.10) np (TN ) ≤ 2 s=0 The geometric sum has the three orders in (D.8). Restricting from N < 2n to n preserves those orders. For the finitely many n < 32, the unit-entry argument in (C.5)–(C.6), with exponent p, gives np (Tn ) ≥ 1, and the constants may be adjusted. Proof of Theorem 1.1. The lower bounds are Theorem C.2. The upper bounds are Lemma D.1, and the middle inequality is (3.2). Corollary D.3 (Optimized squared-error order; restatement of Corollary 1.2). For every ε > 0, within the pure-ε-DP Laplace matrix-mechanism class and over arbitrary finite real factors,   3 log (n + 1) inf MaxSE(ML,R , n) = Θ , Tn =LR ε2  3  log (n + 1) . inf MeanSE(ML,R , n) = Θ Tn =LR ε2 Proof. Every mechanism ML,R is ε-differentially private by Proposition 3.3. Proposition 3.5 identifies the two optimized errors as 2c2 (Tn )2 /ε2 and 2cF (Tn )2 /ε2 , and Theorem 1.1 evaluates both costs at Θ((log(n + 1))3/2 ).

16

Arbitrary Real Factorization Costs for Continual Counting

A P REPRINT

References [1] J. D. Andersson, R. Pagh, T. A. Steiner, and S. Torkamani, Count on Your Elders: Laplace vs Gaussian Noise, 6th Symposium on Foundations of Responsible Computing (FORC), LIPIcs 329, 10:1–10:24, 2025. https://doi.org/10.4230/LIPIcs.FORC.20 25.10 [2] P. Arkhipov and N. P. Kalinin, Improved Error Bounds for Pure Differentially Private Continual Counting via Matrix Factorization, arXiv:2607.08963v1, 2026. DOI: https://doi.org/10.48550/arXiv.2607.08963; https://arxiv.org/abs/2607.08963 v1 [3] K. Bairaktari and K. G. Larsen, The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting, arXiv:2607.00876v2, 2026. DOI: https://doi.org/10.48550/arXiv.2607.00876; https://arxiv.org/abs/2607.00876v2 [4] T.-H. H. Chan, E. Shi, and D. Song, Private and Continual Release of Statistics, ACM Transactions on Information and System Security 14 (2011), No. 3, Article 26. https://doi.org/10.1145/2043621.2043626 [5] C. Dwork, F. McSherry, K. Nissim, and A. Smith, Calibrating Noise to Sensitivity in Private Data Analysis, Theory of Cryptography Conference (TCC), 2006, 265–284. https://doi.org/10.1007/11681878_14 [6] S. Denisov, H. B. McMahan, J. Rush, A. Smith, and A. G. Thakurta, Improved Differential Privacy for SGD via Optimal Private Linear Operators on Adaptive Streams, Advances in Neural Information Processing Systems 35 (NeurIPS), 2022, 5910–5924. https://doi.org/10.52202/068431-0428 [7] C. Dwork, M. Naor, T. Pitassi, and G. N. Rothblum, Differential Privacy under Continual Observation, Symposium on Theory of Computing (STOC), 2010, 715–724. https://doi.org/10.1145/1806689.1806787 [8] A. Edmonds, A. Nikolov, and J. Ullman, The Power of Factorization Mechanisms in Local and Central Differential Privacy, Symposium on Theory of Computing (STOC), 2020, 425–438. https://doi.org/10.1145/3357713.3384297 [9] C. J. Fewster, I. Ojima, and M. Porrmann, p-Nuclearity in a New Perspective, Letters in Mathematical Physics 73 (2005), 1–15; arXiv:math-ph/0412027v3. https://doi.org/10.1007/s11005-005-8445-y [10] H. Fichtenberger, M. Henzinger, and J. Upadhyay, Constant Matters: Fine-Grained Error Bound on Differentially Private Continual Observation, International Conference on Machine Learning (ICML), PMLR 202, 10072–10092, 2023. https: //proceedings.mlr.press/v202/fichtenberger23a.html [11] M. Henzinger, N. P. Kalinin, and J. Upadhyay, Normalized Square Root: Sharper Matrix Factorization Bounds for Differentially Private Continual Counting, 7th Symposium on Foundations of Responsible Computing (FORC), LIPIcs 368, 5:1, 2026; full version arXiv:2509.14334v1. https://doi.org/10.4230/LIPIcs.FORC.2026.5 [12] M. Henzinger, J. Upadhyay, and S. Upadhyay, Almost Tight Error Bounds on Differentially Private Continual Counting, Symposium on Discrete Algorithms (SODA), 2023, 5003–5039; arXiv:2211.05006v2. https://doi.org/10.1137/1.9781611977 554.ch183 [13] A. Hinrichs and A. Pietsch, p-Nuclear Operators in the Sense of Grothendieck, Mathematische Nachrichten 283 (2010), No. 2, 232–261. https://doi.org/10.1002/mana.200910128 [14] S. Kwapień and A. Pełczyński, The Main Triangle Projection in Matrix Spaces and Its Applications, Studia Mathematica 34 (1970), 43–67. https://doi.org/10.4064/sm-34-1-43-67 [15] J.-T. Lapresté, Opérateurs sommants et factorisations. À travers les espaces Lp , Studia Mathematica 57 (1976), 47–83. https://doi.org/10.4064/sm-57-1-47-83 [16] C. Li, G. Miklau, M. Hay, A. McGregor, and V. Rastogi, The Matrix Mechanism: Optimizing Linear Counting Queries under Differential Privacy, The VLDB Journal 24 (2015), No. 6, 757–781. https://doi.org/10.1007/s00778-015-0398-x [17] J. Matoušek, A. Nikolov, and K. Talwar, Factorization Norms and Hereditary Discrepancy, International Mathematics Research Notices 2020, No. 3, 751–780. https://doi.org/10.1093/imrn/rny033 [18] R. Mathias, The Hadamard Operator Norm of a Circulant and Applications, SIAM Journal on Matrix Analysis and Applications 14 (1993), No. 4, 1152–1167. https://doi.org/10.1137/0614080 [19] A. Pietsch, Approximation Spaces, Journal of Approximation Theory 32 (1981), 115–134. https://doi.org/10.1016/0021-904 5(81)90109-X [20] A. Pietsch and J. Wenzel, Orthonormal Systems and Banach Space Geometry, Encyclopedia of Mathematics and its Applications 70, Cambridge University Press, 1998. https://doi.org/10.1017/CBO9780511526145 [21] O. Reinov, Approximation Properties Associated with Quasi-Normed Operator Ideals of (r, p, q)-Nuclear Operators, St. Petersburg Mathematical Society preprint 2017-08, 2017. https://www.mathsoc.spb.ru/preprint/2017/17-08.pdf [22] J. Wenzel, Uniformly Convex Operators and Martingale Type, arXiv:math/0202073v1, 2002. DOI: https://doi.org/10.48550/a rXiv.math/0202073; https://arxiv.org/abs/math/0202073

17