{"id":"d51ee745-5c2a-4380-bdf1-3583514a1d01","arxiv_id":"2412.02840","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"high","formal_verification":"none","parameter_count":0,"one_line_summary":"A claimed explicit matrix factorization using roots of unity would match the best known error bound for private continual counting, but the construction as written does not multiply back to the target matrix.","lead":"The paper proposes a group-algebra method to factor matrices for differentially private continual counting, claiming tighter error bounds for private streaming sums. If the construction were corrected, it would improve the constants that matter for production private learning, but the construction as written does not multiply back to the target matrix.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The proposed factorization cannot hold: setting eR = eL* (conjugate transpose) makes eL eR Hermitian, while M_f is lower-triangular and nonsymmetric; the central identity M_f = eL eR in Section 3.1.2 is false.","rationale":"The central claim of the paper is an explicit factorization M_f = L R with a norm bound. The only proof of the factorization is the construction in Section 3.1.2, which hinges on the equality M_f = eL eR after defining eR = eL*. That equality is not merely unproved; it is impossible for the non-Hermitian lower-triangular matrix M_f whenever eL* denotes conjugate transpose, since eL eL* is always Hermitian. If the authors intended entrywise complex conjugation, the proof's use of Theorem 2.3 and eq. (15) is invalid because the right factor is not the group-pattern function c_f used in the convolution. I checked the n=2 counting case, and both readings fail to reproduce M_f. Because Theorem 1.1 is stated as the main result and Theorem 1.2, Corollary 1.1, and the claimed improvements for counting, sliding window, and striped matrices all depend on it, the paper's central argument does not currently support its conclusions. The separate misattributed Mathias lower bound in Section 2 (Theorem 2.5) is also contradicted by a trivial factorization at n=2, but the Hermitian obstruction alone is decisive. The high-level group-algebra idea might be repairable by defining the right factor directly as a group-pattern matrix with c_f = b_f rather than as eL*, but that is not what the manuscript does, and the verification of the norm bound would need to be redone for such a corrected construction.","tokens_in":24741,"tokens_out":8205,"duration_ms":81385,"concrete_test":"Set n=2, f(0)=f(1)=1, omega = i, construct eL via eq. (17) using any consistent choice of square roots in eq. (16), and set eR = eL* exactly as in Section 3.1.2. Compute the 2x2 product eL eR and compare it with M_f = [[1,0],[1,1]]. Under the conjugate-transpose reading, the product is Hermitian and cannot match. Under the entrywise-conjugate reading, evaluate the (2,1) entry symbolically: it is not identically 1 for principal square roots, so the factorization identity fails. This single symbolic check isolates the load-bearing identity behind Theorem 1.1.","verdict_should_be":"REJECT","load_bearing_attack":"In Section 3.1.2 the paper defines eL by eq. (17) and then sets eR = eL*, immediately using eR[i,j] = (eL[j,i])*, i.e. the conjugate transpose. For any matrix A, the product A A* is Hermitian. But the target matrix M_f defined by eq. (1) is lower-triangular Toeplitz and is not Hermitian in general: for n=2 and f(0)=f(1)=1, M_f = [[1,0],[1,1]] while (M_f)* = [[1,1],[0,1]]. Therefore M_f cannot equal eL eR under this definition. If eL* is instead intended as entrywise conjugation, then the product is not the group-pattern convolution used in the proof: the right factor has entries conj(b_f(omega^{k-j})) rather than c_f(omega^{j-k}), so eq. (15) does not apply and no argument establishes M_f = eL eR. Under either reading, the claimed factorization at the top of page 11 is false or unsupported, so the bound (4) in Theorem 1.1 and the algorithmic consequences in Theorem 1.2 do not follow. A separate supporting error: Theorem 2.5 is quoted as a lower bound of Mathias, but at n=2 the trivial factorization M_count = [[1,0],[1,1]] * I gives gamma_2 <= sqrt(2), contradicting the claimed lower bound of about 2.12; Mathias's bound is an upper bound. This reinforces that the main construction is not correct as written.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a group-algebra approach to explicitly factor lower-triangular Toeplitz matrices M_f arising in differentially private weighted prefix sums under continual observation. The authors view M_f as a principal submatrix of a 2n×2n group-pattern matrix over the 2n-th roots of unity, define polynomials a_f and b_f from the evaluations of the symbol m_f(ω^ℓ), and claim a factorization M_f = eL eR with the norm bound γ^(p)(M_f) ≤ (1/(2n^{1-1/p})) Σ_{ℓ=0}^{2n-1} |m_f(ω^ℓ)|. This is used to derive improved upper bounds for counting, sliding-window, and striped matrices, and to instantiate the matrix mechanism for differentially private continual observation.","tokens_in":25096,"tokens_out":17911,"duration_ms":161344,"significance":"If the main theorem were correct, the paper would give the first explicit factorization matching the best-known non-constructive γ₂ bound for the counting matrix, improve on prior constructive factorizations, and provide the first upper bound for the sliding-window matrix for arbitrary real weight functions. The group-algebra viewpoint is a fresh and potentially reusable idea, and the intended Algorithm 1 is genuinely explicit. However, the central algebraic identity in Section 3.1.2 is false as written, and a cited theorem in Section 2.2.3 is misstated; consequently the main claims are not currently established despite the elegance of the approach.","major_comments":[{"comment":"The claimed factorization M_f = eL eR is false under the definitions given. Since eR is set to eL* (the conjugate transpose), the product eL eR = eL eL* is Hermitian, while M_f is lower-triangular Toeplitz and is not Hermitian in general: for n = 2 and f(0) = f(1) = 1, M_f = [[1,0],[1,1]] is not Hermitian. Thus the identity used to prove Theorem 1.1 and the correctness of Algorithm 1 does not hold. The subsequent step '(eL[j,i])* = bf(ω^{j-i})' is also unjustified: for bf(x) = (1/2n) Σ ζ_ℓ x^ℓ, the conjugate of bf(ω^{i-j}) equals (1/2n) Σ conj(ζ_ℓ) ω^{ℓ(j-i)}, which equals bf(ω^{j-i}) only if every ζ_ℓ is real, and ζ_ℓ = sqrt(mf(ω^ℓ)) is generally complex. A correct right factor would be the group-pattern matrix with entries eR[i,j] = bf(ω^{j-i}) for 1 ≤ i ≤ 2n and 1 ≤ j ≤ n; with that choice the group-convolution identity (15) would apply, but the norm estimates in Claims 3.1 and 3.2 would need to be re-derived for the new eR rather than following from eR = eL*.","section":"Section 3.1.2, Eq. (17)"},{"comment":"Theorem 2.5 misstates the direction of Mathias's bound. The displayed quantity with n = 2 equals (3/4)(|csc(π/4)| + |csc(3π/4)|) = (3/4)·2√2 ≈ 2.12, but γ₂(M_count) ≤ √2 via the trivial factorization M_count = [[1,0],[1,1]]·I, so the bound cannot be a lower bound; in Mathias's paper Corollary 3.5 is an upper bound on γ₂(M_count). This error propagates directly into Theorem 6.1, where the first term in eq. (25) is asserted as a lower bound on γ₂(M_sliding) and is not valid; only the Matoušek et al. lower bound in eq. (10) is valid. Please correct the direction of Theorem 2.5, update the discussion in Section 1.2 and Remark 1.3, and revise Theorem 6.1 accordingly.","section":"Section 2.2.3, Theorem 2.5"}],"minor_comments":[{"comment":"There are typos in the title and abstract ('DIFFERENTIALL Y PRIV A TE', 'Differentiall y'); these should be corrected.","section":"Title and Abstract"},{"comment":"The set F is introduced as 'non-negative valued functions', but Theorem 1.1 and the introduction claim the result for all real-valued f; please reconcile the domain of the theorem with the definition of F.","section":"Section 1, Definition of F"},{"comment":"For the sliding-window matrix, Eq. (5) defines M_sliding[i,j] = 1 for 0 ≤ i−j ≤ W, which gives W+1 nonzero diagonals, while the text writes the polynomial as 1 + x + ... + x^{W−1} and the bound uses the numerator 1−ω^{Wℓ}; this off-by-one discrepancy should be fixed and the bounds restated consistently.","section":"Section 5 and Corollary 1.1"},{"comment":"In the first case of the proof of Eq. (14), the term for k = d is written as 'Σ_{ℓ=0}^{2n-1} f(d)' but should be '2n·f(d)' before division by 2n; this is a typographical slip in an otherwise clear calculation.","section":"Section 3.2, proof of Eq. (14)"},{"comment":"The real-valued factor bR is defined in Eq. (21) as a vertical stacking of eRr and −eRc, but Algorithm 1 writes 'bR = [ eRr − eRc ]*' with a star, which is inconsistent with the surrounding text and notation; please align the algorithm with Eq. (21).","section":"Section 4.1 and Algorithm 1, line 3"},{"comment":"Eq. (8) uses σ_{ε,δ} = (2Δ/ε)√ln(1.25/δ), while Definition 2.1 and Theorem 2.7 use a different expression σ_{ε,δ} = (2/ε)√(4/9 + ln((1/δ)√(2/π))); the paper should state which Gaussian mechanism is being used and ensure the constants are consistent throughout.","section":"Theorem 1.2 vs. Definition 2.1"}],"recommendation":"major_revision","confidential_remarks":"The central factorization appears repairable: replacing eR = eL* with the group-pattern right factor eR[i,j] = bf(ω^{j-i}) would make the product equal to M_f by Theorem 2.3, and the DFT orthogonality calculations show the norm bounds in Claims 3.1 and 3.2 would still go through. However, the manuscript as submitted contains a false identity in the main proof and a reversed cited theorem, so it cannot be accepted in its current form. I would encourage the editor to request a revision rather than reject, provided the authors can supply the corrected factorization and re-derive the norm estimates without changing the statement of Theorem 1.1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know two things about this paper: the group-algebra approach is genuinely new and potentially useful, and the central factorization as stated is wrong. The authors set the right factor eR to the conjugate transpose of eL, so eL eR is Hermitian. But M_f is lower-triangular and generally not symmetric. For n=2 and f(0)=f(1)=1, the product cannot equal [[1,0],[1,1]]. That is not a small slip; the proof of Theorem 1.1 relies on this identity.\n\nWhat is actually new: encoding M_f as a principal submatrix of a group-pattern matrix over the 2n-th roots of unity, then factoring via convolution on the group. That is a real departure from the Toeplitz-operator approach in prior work. And if the right factor is defined directly as b_f(omega^{j-i}) instead of the conjugate transpose, the convolution calculation in Section 3.3 goes through, and the norm bounds in Claims 3.1 and 3.2 likely still hold. So the high-level construction is close to something that works, and the claimed bounds (matching Mathias's upper bound, first sliding-window factorization) are not absurd.\n\nThe paper also misquotes Mathias's result as a lower bound. At n=2, the trivial factorization M_count = [[1,0],[1,1]] * I gives gamma_2 <= sqrt(2), contradicting the claimed csc-sum lower bound of about 2.12. That is a separate load-bearing error, since Theorem 6.1 builds on it.\n\nMy take: this should not be published as submitted. The central theorem is unproven because the factorization does not multiply to M_f. But the idea is worth taking seriously. I would not cite it in its current form, and I would not use the bounds without checking a corrected version. If I were an editor, I would send it to peer review because the approach is novel and a fix seems plausible; the referees would likely ask for major revision or rejection with an invitation to resubmit.","headline":"Novel group-algebra framing for continual observation, but the central factorization is false as written; the idea may be repairable but the current proof does not work.","tokens_in":25613,"tokens_out":5916,"would_cite":false,"duration_ms":54749,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68P27","15A60","15B05"],"pacs":[],"model":"deepseek-v4-flash","headline":"Explicit factorization of weighted prefix sums matches best non-constructive error bound.","keywords":["differential privacy","continual observation","factorization norms","matrix mechanism","group-pattern matrices","weighted prefix sums","sliding window","Toeplitz matrices"],"falsifier":"Take $n=3$ with $f(0)=1$, $f(1)=2$, $f(2)=4$; then $M_f[2,1]=2$ and $M_f[1,2]=0$. Constructing $\\tilde L$ by eq. (17) with $b_f$ from eq. (16) forces the product $\\tilde L\\tilde L^*$ to be Hermitian, so its $(1,2)$ and $(2,1)$ entries are equal and it cannot equal the non-symmetric $M_f$; checking this entry pair for any non-symmetric $f$ settles the factorization identity as written.","tokens_in":24489,"feed_emoji":"🔐","tokens_out":13208,"duration_ms":124538,"temperature":0.7,"pith_summary":"The paper aims to prove that every weighted prefix-sum matrix $M_f$ -- the lower-triangular matrix whose entries are $f(i-j)$ for $i\\ge j$ -- has an explicit, efficiently computable factorization $M_f=LR$ whose factorization norm is at most $\\frac{1}{2n^{1-1/p}}\\sum_{\\ell=0}^{2n-1}|m_f(\\omega^\\ell)|$, where $m_f(x)=\\sum_{k=0}^{n-1}f(k)x^k$ and $\\omega$ is a primitive $2n$-th root of unity. This matters because factorization norms control the additive error of the Gaussian matrix mechanism used to release weighted prefix sums under differential privacy: smaller norm means smaller noise for the same privacy guarantee. If the claim is correct, the construction matches the best-known non-constructive upper bound for the unweighted counting matrix, gives the first explicit factorization for sliding-window matrices, and works for arbitrary real-valued weight functions rather than only monotone positive ones. The motivating application is production private next-word prediction, where the weighted-sum step multiplies the model dimension and any constant-factor improvement in noise is practically significant.","feed_headline":"Explicit factorization of weighted prefix sums matches best error bound","feed_subtitle":"One average over the roots of unity sets the ℓ_p error of private continual observation for any weight function.","key_machinery":"The load-bearing object is the group-pattern matrix: given a finite group $G$ with listed elements $g_1,\\dots,g_k$ and a function $h:G\\to\\mathbb{C}$, the matrix has $(i,j)$-entry $h(g_i^{-1}g_j)$. The paper uses the cyclic group of $2n$-th roots of unity, defines $h=a_f$ as in eq. (13), and applies the group-product theorem that a product of two group-pattern matrices is again a group-pattern matrix with the convolution of their defining functions. The proof sets the two factor functions to the square root, $b_f(x)=c_f(x)=\\frac{1}{2n}\\sum_{\\ell=0}^{2n-1}\\sqrt{m_f(\\omega^\\ell)}\\,x^\\ell$, takes the right factor to be the conjugate transpose of the left factor, and then uses the orthogonality of roots of unity. The theorem converts the entire factorization problem into one scalar identity on the group, which is why the final bound is just an average of $|m_f(\\omega^\\ell)|$ and why no convex program is needed.","core_discovery":"The core discovery is a new route from weighted prefix sums to group algebra. The paper embeds the $n\\times n$ Toeplitz matrix $M_f$ as a principal submatrix of a $2n\\times 2n$ group-pattern matrix built from a cyclic group of order $2n$: with $\\omega$ a primitive $2n$-th root of unity and $a_f(x)=\\frac{1}{2n}\\sum_{\\ell=0}^{2n-1}m_f(\\omega^\\ell)x^\\ell$, the entry $a_f(\\omega^{j-i})$ reproduces $M_f$ on the first $n$ rows and columns. The factorization is obtained by writing $b_f(x)=c_f(x)=\\frac{1}{2n}\\sum_{\\ell=0}^{2n-1}\\sqrt{m_f(\\omega^\\ell)}\\,x^\\ell$ and using the theorem that the product of two group-pattern matrices is again a group-pattern matrix whose defining function is the group convolution of the two functions. The factors are then converted from complex to real and made lower-triangular by an orthogonal-triangular decomposition, yielding an explicit algorithm rather than a convex optimization. The result is a single average bound for all $\\gamma^{(p)}(M_f)$, $p\\in[2,\\infty)$, stated directly in terms of the values of the weight polynomial on the roots of unity.","pith_inferences":["A testable extension is to minimize the same average over other cyclic groups of order $2n$: the paper's remark allows any generator $g$, so one can search for the generator minimizing $\\sum_\\ell |m_f(g^\\ell)|$ and potentially beat the root-of-unity choice for structured weight functions.","Because the bound is a Fourier average of the weight function, it suggests a design heuristic for private weighted sums: weight functions with small discrete Fourier magnitudes on the $2n$-th roots of unity have small additive error, so approximating a desired weight function by one with such a spectrum could reduce noise before privacy is applied.","The same lifting applies to any linear query matrix that is a principal submatrix of a group-pattern matrix, not just Toeplitz prefix sums; candidates include circulant or near-circulant query families, for which the group-convolution theorem would supply an explicit factorization without optimization."],"forward_implications":["For the unweighted counting matrix, $\\gamma_2(M_{\\text{count}}) \\le 1+\\ln(n)/\\pi$, matching the best-known non-constructive upper bound and improving the previous constructive bound by the Euler-Mascheroni constant divided by $\\pi$.","For the sliding-window matrix with window size $W$, the bound $\\gamma_2(M_{\\text{sliding}}) \\le \\frac{1}{2n}\\sum_{\\ell=0}^{2n-1}\\left|\\frac{1-\\omega^{W\\ell}}{1-\\omega^\\ell}\\right|$ is the first explicit factorization and upper bound for this matrix.","For the $b$-striped matrix, $\\gamma_2(M_{\\text{striped}}) \\le 1+\\frac{1}{\\pi}\\ln(n/b)$, improving the previous constructive bound by the same constant as in the counting case.","For any real-valued weight function $f$ and any $p\\ge 2$, the paper's mechanism has $\\ell_p$ error at most $\\sigma_{\\epsilon,\\delta}\\min\\{\\sqrt{p},\\sqrt{\\ln n}\\}\\cdot \\frac{1}{2n^{1-1/p}}\\sum_{\\ell=0}^{2n-1}|m_f(\\omega^\\ell)|$, so the same bound controls both expected error and high-probability tails.","The construction removes the monotonicity and positivity restrictions of earlier weighted-sum frameworks, so windowed, striped, and arbitrary real-valued weight functions are handled by the same explicit factorization."],"supporting_citations":[{"why":"Supplies the theorem that a product of group-pattern matrices is again a group-pattern matrix, the engine that turns the factorization into a convolution identity.","marker":"[10]"},{"why":"Introduces the group-matrix object into which the paper embeds the weighted prefix-sum matrix.","marker":"[16]"},{"why":"Provides the reduction making a Gaussian mechanism with lower-triangular factors private against adaptive streams, plus the orthogonal-triangular decomposition trick for real conversion.","marker":"[17]"},{"why":"The previous efficient near-optimal factorization for continual counting; supplies the comparison baseline and the closed-form expression of the non-constructive bound.","marker":"[19]"},{"why":"The previous best constructive bound for the counting and striped matrices that the new factorization improves.","marker":"[27]"},{"why":"The prior general framework for weighted sums, whose monotonicity restrictions and Bell-polynomial bounds the paper removes.","marker":"[34]"},{"why":"Establishes the relation between the factorization norms $\\gamma^{(p)}$ and the $\\ell_p$ additive error of the Gaussian matrix mechanism.","marker":"[42]"},{"why":"The non-constructive upper bound for the counting matrix that the new constructive bound matches.","marker":"[43]"}],"fun_headline_variants":["Group algebra matches best known error for private prefix sums","Roots of unity unlock optimal private continual observation","Dedekind and Schur meet differential privacy for prefix sums","Explicit factorization hits optimal bound for private weights","First efficient factorization for private sliding window sums"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The proof assumes that the right factor can be taken as the conjugate transpose of the left factor, but for a real matrix $M_f$ this makes the product necessarily symmetric while $M_f$ is lower-triangular and generally not symmetric, so the equality can hold only in special cases.","fun_headline_variants_meta":{"raw":{"variants":["Group algebra matches best known error for private prefix sums","Roots of unity unlock optimal private continual observation","Dedekind and Schur meet differential privacy for prefix sums","Explicit factorization hits optimal bound for private weights","First efficient factorization for private sliding window sums"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00063,"raw_usage":{"total_tokens":3024,"prompt_tokens":1172,"completion_tokens":1852,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":788,"completion_tokens_details":{"reasoning_tokens":1777}},"tokens_in":788,"tokens_out":1852,"duration_ms":14074,"temperature":1.0,"reasoning_tokens":1777,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T23:07:43.423136+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take $n=3$ with $f(0)=1$, $f(1)=2$, $f(2)=4$; then $M_f[2,1]=2$ and $M_f[1,2]=0$. Constructing $\\tilde L$ by eq. (17) with $b_f$ from eq. (16) forces the product $\\tilde L\\tilde L^*$ to be Hermitian, so its $(1,2)$ and $(2,1)$ entries are equal and it cannot equal the non-symmetric $M_f$; checking this entry pair for any non-symmetric $f$ settles the factorization identity as written.","supporting_citations":[{"cited_title":"A matrix-oriented approach to group algebras, 1976","cited_arxiv_id":null,"evidence_quote":"Supplies the theorem that a product of group-pattern matrices is again a group-pattern matrix, the engine that turns the factorization into a convolution identity."},{"cited_title":"Aus briefen an Frobenius https://rcin.org.pl/dlibra/publication/171804/edition/ 140750/content, 1882","cited_arxiv_id":null,"evidence_quote":"Introduces the group-matrix object into which the paper embeds the weighted prefix-sum matrix."},{"cited_title":"Brendan McMahan, Krishna Pillutla, Thomas Steinke, and Abhradeep Thakurta","cited_arxiv_id":null,"evidence_quote":"The previous efficient near-optimal factorization for continual counting; supplies the comparison baseline and the closed-form expression of the non-constructive bound."},{"cited_title":"Constant matters: Fine-grained error bound on differentially private continual observation","cited_arxiv_id":null,"evidence_quote":"The previous best constructive bound for the counting and striped matrices that the new factorization improves."},{"cited_title":"A unifying framework for differentially private sums under continual observation","cited_arxiv_id":null,"evidence_quote":"The prior general framework for weighted sums, whose monotonicity restrictions and Bell-polynomial bounds the paper removes."},{"cited_title":"The hadamard operator norm of a circulant and applications","cited_arxiv_id":null,"evidence_quote":"The non-constructive upper bound for the counting matrix that the new constructive bound matches."}],"review_version":1}