{"id":"af782387-2f5e-4ab5-a6f0-be2469cd8470","arxiv_id":"2411.15454","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For Gaussian trace estimation, the worst tail probabilities among matrices with fixed effective rank or bounded norm pair are governed by Gamma distributions, but the tail-region thresholds remain unproven.","lead":"This paper asks which symmetric matrices make the standard Gaussian trace estimator fail most often, and derives worst-case tail bounds for two matrix families. The practical message is that a Gamma distribution captures the worst case, but the exact error threshold where those bounds start is still conjectured.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The advertised quantitative extremal bounds are conditional on unproven threshold conjectures; without locating ε_rel and ε_abs, Theorems 6-7 do not yield the claimed practical bounds.","rationale":"The reader's CONDITIONAL verdict is appropriate. The paper's genuine contribution is the majorization framework, especially Theorem 4 for indefinite matrices, and the overall approach is a legitimate route to extremal bounds. But the central advertised results, Theorems 6 and 7, are not fully derived: the thresholds are explicitly conjectural, and the infinite-divisibility step in Section 3.3 is asserted rather than proved. These are exactly the places where the Gamma worst-case bounds would be established, so the concern is load-bearing rather than cosmetic. I do not see internal inconsistency in the majorization proofs themselves, and the paper is honest about the conjectures, but the abstract and Section 5 overstate what is proven. My read does not move the verdict: it remains CONDITIONAL, requiring either proofs of Conjectures 1-4 or a rigorous limiting argument for the generalized Gamma families.","tokens_in":49,"tokens_out":17828,"duration_ms":352141,"concrete_test":"Test Conjecture 1 directly: for α=β=1 and μ=3/2, maximize the mode of Q_λ+λ_1ψ+λ_2ψ′ over two-coordinate weight vectors with λ_1+λ_2=1 and 0≤λ_i≤1/μ, using exact density evaluation and root finding; if any feasible λ gives mode > 1+1/μ = 5/3, Conjecture 1 is false. In parallel, for m=2 and μ=3/2, form A_rel(μ)=diag(2/3,1/3) and compute Pr(|tr_m^G(A_rel)−1|≥ε) exactly for ε≥2/(mμ)=2/3; a violation of the Gamma(mμ/2,mμ/2) bound would refute Conjecture 3 and the advertised quantitative form of Theorem 6.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central quantitative claim is undercut by an admitted gap. Theorem 6 and Theorem 7 assert existence of thresholds ε_rel and ε_abs and then give Gamma tail bounds for all larger ε. But the proof path requires Conjectures 1 and 2, which locate where the majorization-ordering tails begin, and the paper only proves the opposite inequalities in Theorem 3 and Theorem 5. Section 1.2 states explicitly that the exact tail-region start has so far been beyond the author's ability to prove. Conjectures 3 and 4, the actual numbers one would use, are therefore unproven. Since the abstract and Section 5 present these as derived extremal bounds, the practical content is conditional on unresolved conjectures. A second gap sits in Section 3.3: the infinite-divisibility limiting argument, used to extend the fixed-(α,β) majorization theorems to the generalized families Q_rel(µ) and Q_abs(λ,φ), is asserted without a formal limit or continuity argument. Lemma 3 gives the useful inclusion for finite T, but the converse approximation statement that lets bounds pass to the limit is not proved. Both gaps sit exactly at the point where the Gamma worst-case bound is supposed to be established.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies tail probabilities of the Gaussian trace estimator for real symmetric matrices. It introduces eigenvalue majorization orders for two matrix families (positive semidefinite matrices with bounded effective rank, and symmetric matrices with bounded 2-norm and fixed Frobenius norm), proves CDF monotonicity in the tail regions (Theorems 2 and 4), identifies candidate extremal matrices (A_rel and A_abs), and proposes Gamma-distribution worst-case bounds for relative and absolute errors (Theorems 6 and 7). The paper is transparent that the exact locations of the tail regions are not proved: Section 1.2 states that it has so far been beyond the author's ability to prove where these regions begin, and the practical thresholds are left as Conjectures 3 and 4. The passage to the limiting Gamma families via infinite divisibility in Section 3.3 is also asserted rather than formally justified. The advertised practical bounds are therefore conditional, although the majorization framework and the proofs of Theorems 2 and 4 are substantial.","tokens_in":115,"tokens_out":12114,"duration_ms":177925,"significance":"If the conjectured threshold locations and the infinite-divisibility approximation were established, the paper would provide essentially tight, parameter-free worst-case tail bounds with explicit extremizers, and the absolute-error result for indefinite matrices (Theorem 4 with Lemma 2) appears to be novel. The Laplace-transform and unimodality machinery is elegant, and the proofs of Theorems 2 and 4, apart from the threshold questions, are credible. The paper is also unusually candid about its own limitations, which helps the reader separate what is proved from what is conjectured. However, the central practical content of Theorems 6 and 7 is not yet derived: the thresholds epsilon_rel and epsilon_abs are unknown, and the limiting step from fixed (alpha,beta) families to the general families Q_rel(mu) and Q_abs(lambda,phi) lacks a formal argument. The current contribution is therefore a promising framework plus conditional results, not a complete derivation of the advertised extremal bounds.","major_comments":[{"comment":"The central practical statements are conditional on unproven threshold conjectures. Theorem 6 asserts existence of epsilon_rel and Theorem 7 asserts existence of epsilon_abs, but no location for these thresholds is proved. Section 1.2 explicitly states that it has so far been beyond the author's ability to prove exactly where the tail regions begin. The values in Conjecture 3 (epsilon_rel <= 2/(m mu)) and Conjecture 4 (epsilon_abs <= 2 lambda/m + sqrt(2 phi^2/m + (2 lambda/m)^2)) are precisely the missing locations, and Theorems 3 and 5 give only pessimistic lower bounds on xupper and xhat_upper, i.e., bounds in the opposite direction. Consequently the chains of inequalities in Theorems 6 and 7 do not yield usable bounds until these conjectures are resolved. Either prove the conjectures or provide an alternative way to locate the tail regions, or revise the abstract and Section 5 to present these as conditional results.","section":"Section 1.2, Theorems 6-7, Conjectures 3-4"},{"comment":"The infinite-divisibility limit used to pass from the fixed-parameter families Q_rel(mu; alpha,beta) and Q_abs(lambda,phi; alpha,beta) to the general families Q_rel(mu) and Q_abs(lambda,phi) is not formally justified. Lemma 3 proves only the inclusion Q_rel(mu; alpha,beta) subset of Q_rel(mu; alpha/T,beta), and similarly for Q_abs. The subsequent claim that, for sufficiently large T, the fixed-parameter sets contain distributions arbitrarily close to any distribution in Q_rel(mu) or Q_abs(lambda,phi), and that therefore any bounds pass to the limit, requires a topology on the distribution families and a continuity argument for the supremal tail probability. No such argument is given. Since the identification of the extremal Gamma distributions in (4) and (5) rests on this step, it is load-bearing for Theorems 6 and 7.","section":"Section 3.3"},{"comment":"The chain of reasoning leading to Theorems 6 and 7 is not fully traced. The text states that 'employing the infinite division strategy of Section 3.3' shows that the Gaussian trace estimators for A_rel and A_abs are tail-bounded by the Gamma distributions in (4) and (5), but this step is not expanded. In particular, it is not shown that the extremal element of Q_rel(mu) or Q_abs(lambda,phi) is indeed the claimed Gamma variable, nor that the majorization monotonicity of Theorems 2 and 4 survives the limiting construction. A rigorous proof should either derive (4) and (5) directly from Lemma 3 with an explicit approximation argument or state the required limit theorem.","section":"Section 5, first paragraph"}],"minor_comments":[{"comment":"The phrase 'derives extremal tail bounds' overstates the proven content; consider rewording to indicate that the bounds are derived conditional on conjectured tail-region locations, or add a caveat near Theorems 6 and 7.","section":"Abstract and Section 5"},{"comment":"The inequality '0 < lambda <= 1/sqrt(alpha) phi' is not readable as printed; based on Theorem 4 it is presumably meant to be '0 < lambda <= phi/sqrt(alpha)', and the displayed formula should be corrected.","section":"Definition 10"},{"comment":"The statement contains a typographical artifact ('bracehtipupleft /bracehtipdownright') in the repeated vector; the intended notation with an underbrace or similar should be restored.","section":"Lemma 3"},{"comment":"References [5] and [6] appear to be the published and preprint versions of the same work; please merge them or note the relationship explicitly.","section":"References"},{"comment":"The step 'by the definition of xhat_upper, the density function is convex on (xhat_upper, infinity)' would benefit from a sentence explaining why the second derivative cannot change sign again after its last inflection point; otherwise the reader cannot see that convexity, rather than mere absence of inflection points, is guaranteed.","section":"Appendix A.2, proof of Theorem 4"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is honest about its conjectural steps, but the abstract and Section 5 present the practical bounds as though they are derived. If the author can resolve Conjectures 1 and 2, or alternatively reframe the paper explicitly as conditional results with the conjectures labeled as open problems and with the infinite-divisibility limit fully justified, the paper would be a solid contribution. The absolute-error majorization machinery (Lemma 2 and Theorem 4) is the most novel part and deserves careful checking. I recommend major revision rather than rejection because the framework is plausible and the missing pieces are identifiable and potentially fixable."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear [Colleague],\n\nThe headline: this paper has a real new idea—an F-majorization order that gives absolute-error tail comparisons for indefinite matrices with fixed Frobenius norm—but the advertised quantitative bounds are conditional on unproven conjectures, and the author says so clearly.\n\nWhat's new: Theorem 4 and Definition 5 are genuinely new relative to the cited literature. The relative-error theorem is a restatement of [8]; the author says that too. The Laplace-transform/unimodality proof strategy is plausible, and the majorization lemma for the F-order (Lemma 2) does real work.\n\nWhere it's soft: Theorems 6 and 7, which are the practical payoff, require knowing where the tails begin—exactly the thing left as Conjectures 1 and 2. The author admits in Section 1.2 that proving the tail-region location is beyond him, and Theorems 3 and 5 only give the pessimistic direction. Without the conjectures, the Gamma worst-case bounds hold only for unknown error tolerances, so the abstract's claim to \"derive extremal tail bounds\" oversells what is proved. The infinite-divisibility approximation in Section 3.3 is also asserted rather than proved; Lemma 3 gives the inclusion for finite T, but the limiting step that transfers bounds to Qrel(µ) and Qabs(λ,φ) is not formalized. These are real gaps, but they are explicitly acknowledged, not concealed.\n\nThe honest read: the paper is a solid theoretical contribution that pushes the majorization technique to indefinite matrices and identifies precisely where the open problems are. The conjectures are clearly stated and some are numerically plausible. The practical improvements over Cortinovis-Kressner are likely minor, as the author himself says in the conclusion.\n\nWho it's for: researchers working on trace estimation or extremal probabilities of linear combinations of Gamma variables. A referee can engage with the majorization proofs and the conjectures without being misled. Worth peer review, but the editor should ask for revision to make clear that Theorems 6-7 are conditional, or to prove the conjectures.","headline":"Genuinely new F-majorization result for indefinite matrices, but the advertised quantitative bounds are conditional on unproven tail-location conjectures; worth refereeing as a solid contribution with honest limitations.","tokens_in":12819,"tokens_out":2675,"would_cite":true,"duration_ms":21566,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60E15","15A42"],"pacs":[],"model":"deepseek-v4-flash","headline":"The worst-case tail of the Gaussian trace estimator over any spectral constraint considered here is a Gamma tail, provided the conjectured threshold for the tail region holds.","keywords":["Gaussian trace estimation","extremal tail bounds","majorization","Gamma random variables","effective rank","stable rank","indefinite matrices","randomized numerical linear algebra"],"falsifier":"Take the explicit worst-case matrix $A_{\\mathrm{rel}}(\\mu)$ of (2), fix $m$, and evaluate the tail probability at $\\varepsilon = 2/(m\\mu)$; if $\\Pr(|\\mathrm{tr}_m^G(A)-\\mathrm{tr}(A)| \\ge \\varepsilon\\,\\mathrm{tr}(A))$ exceeds $\\Pr(|X-1|\\ge \\varepsilon)$ with $X\\sim \\mathrm{Gamma}(m\\mu/2,m\\mu/2)$, then Conjecture 3 is false and Theorem 6's stated range collapses. The analogous absolute test evaluates $\\varepsilon = 2\\lambda/m + \\sqrt{2\\varphi^2/m + (2\\lambda/m)^2}$ against $2\\Pr(X-\\mathbb{E}[X]\\ge \\varepsilon)$ with $X\\sim \\mathrm{Gamma}(m\\rho/2,m/(2\\lambda))$.","tokens_in":11837,"feed_emoji":"📊","tokens_out":12540,"duration_ms":100744,"temperature":0.7,"pith_summary":"This paper seeks the worst possible tail behavior of the Gaussian trace estimator, the randomized estimator $\\frac{1}{m}\\sum_{j=1}^{m} z_j^T A z_j$ for the trace of a real symmetric matrix $A$. The claim is that, among all positive semidefinite matrices with a given effective rank, and among all symmetric matrices with a given 2-norm and Frobenius norm, a single maximally skewed spectrum dominates every other spectrum in the majorization order, and the estimator's tails are then bounded by those of a Gamma variable. If the claim is right, sample sizes for relative or absolute error tolerances can be read from Gamma quantiles rather than from looser concentration inequalities. The majorization and extremal-matrix parts are proved; the exact place where the Gamma bound starts to apply is left as Conjectures 1 and 2, so the practical range of the bounds is not yet established.","feed_headline":"Gaussian trace estimator's worst tail is a Gamma tail","feed_subtitle":"Worst tail belongs to one extreme spectrum; where that bound starts is unproved.","key_machinery":"The argument runs on the majorization order on eigenvalues—partial sums of the largest entries dominate those of a less-skewed vector with the same total—extended in Definition 5 to an indefinite version using squared positive and negative parts. Lemmas 1 and 2 decompose any majorization step into transfers between two coordinates, so CDFs can be compared along a linear interpolation $Y(t)$. The Laplace transform of the CDF reduces the comparison to the sign of a derivative of a density of the form $Y(t)+\\nu_j\\psi+\\nu_k\\psi'$, where $\\psi,\\psi'$ are exponential; unimodality (relative error) or convexity (absolute error) of that density determines where in the tail the ordering holds. Infinite divisibility of Gamma variables then lets the discrete $m$-sample chi-squared structure be replaced, in the limit, by general finite linear combinations of Gamma variables, yielding the Gamma worst cases in (4) and (5).","core_discovery":"On the author's own terms, the central result is that the Gaussian trace estimator's tail probabilities are extremized by specific spectra, and these extremal tails are Gamma-distributed. For a nonzero SPSD matrix $A$ with effective rank $\\mu = \\mathrm{reff}(A)$, Theorem 6 states there is a threshold $\\varepsilon_{\\mathrm{rel}}$ such that for every $\\varepsilon \\ge \\varepsilon_{\\mathrm{rel}}$, $$\\Pr(|\\mathrm{tr}_m^G(A)-\\mathrm{tr}(A)| \\ge \\varepsilon\\,\\mathrm{tr}(A)) \\le \\Pr(|X-1|\\ge \\varepsilon),$$ with $X \\sim \\mathrm{Gamma}(m\\mu/2, m\\mu/2)$. For a symmetric $A$ with $\\|A\\|_2=\\lambda$ and $\\|A\\|_F=\\varphi$, Theorem 7 states there is a threshold $\\varepsilon_{\\mathrm{abs}}$ such that for every $\\varepsilon \\ge \\varepsilon_{\\mathrm{abs}}$, $$\\Pr(|\\mathrm{tr}_m^G(A)-\\mathrm{tr}(A)| \\ge \\varepsilon) \\le 2\\Pr(X-\\mathbb{E}[X]\\ge \\varepsilon),$$ with $X \\sim \\mathrm{Gamma}(m\\rho/2, m/(2\\lambda))$ and $\\rho=\\varphi^2/\\lambda^2$. The specific worst-case matrices are (2) and (3). Theorems 6 and 7 are conditional on the tail regions actually starting at the conjectured thresholds, since the author proves only pessimistic lower bounds in Theorems 3 and 5 and leaves Conjectures 1 and 2 open.","pith_inferences":["If Conjectures 1 and 2 are proved, the Gamma bounds become explicit minimax statements over the matrix class: within the tail region, no matrix with the same spectral summary statistics can force a larger tail probability than the displayed Gamma worst case, making the bounds usable as certificates in sample-size arguments.","The same two-coordinate interpolation machinery could locate the missing thresholds: Conjectures 1 and 2 are statements about the first point where a density of a Gamma mixture plus two exponentials stops being monotone or convex, so they could be settled by a one-dimensional optimization over the two-coordinate transfer rather than by a new proof idea.","A numerical extension would test whether the majorization ordering also holds for the normalized Gaussian estimator, where each sampled vector is divided by its length; the Gamma structure is lost, but the same interpolation and Laplace-transform comparison might still order the tails, which the paper notes is plausible.","A direct simulation at the conjectured threshold would settle the practical value of the bounds quickly: for a noninteger effective rank, the empirical tail probability of the extremal matrix at $\\varepsilon=2/(m\\mu)$ can be compared with the Gamma bound before any new theorem is attempted. "],"forward_implications":["For SPSD matrices, the relative-error bound depends on the product $m\\,\\mathrm{reff}(A)$, so increasing the effective rank has the same tail effect as increasing the sample count.","For indefinite matrices, the absolute-error bound is governed by the stable rank $\\rho=\\varphi^2/\\lambda^2$; if Conjecture 4 holds, the tolerance needed for the bound to apply shrinks to $\\varphi$ as $m\\to\\infty$.","The extremal spectra are explicit and universal within their classes: (2) for relative error, (3) for absolute error, and its negative for the lower tail.","Within the tail region these bounds are tighter than the existing concentration inequalities, though the size of that region remains conjectural.","The absolute bound carries a factor 2 because the upper and lower tails are controlled by opposite extremal matrices, $A_{\\mathrm{abs}}$ and $-A_{\\mathrm{abs}}$. "],"supporting_citations":[{"why":"Supplies the concentration bound (Theorem 1) and the effective-rank corollary that the paper aims to tighten.","marker":"[1]"},{"why":"Provides the majorization result for nonnegative sums of Gamma variables that Theorem 2 restates.","marker":"[8]"},{"why":"Extends extremal probabilities to sums of Gamma variables with arbitrary shape and scale, used for the sampling-number and infinite-division arguments.","marker":"[9]"},{"why":"Gives extremal probabilities for Gaussian quadratic forms and the unimodality of such distributions used in the density-sign argument.","marker":"[10]"},{"why":"Supplies the two-coordinate decomposition lemma for majorization used to reduce comparisons to pairwise transfers.","marker":"[7]"},{"why":"Used in the conclusion to translate the tightened bounds into sample counts for Frobenius-norm and trace estimation.","marker":"[5]"}],"fun_headline_variants":["Gaussian trace worst tail is Gamma if thresholds hold","Extremal Gaussian trace tails are Gamma, if conjectures hold","Worst-case spectra give Gamma tails if conjectures hold","Worst tail for Gaussian trace: Gamma, conjecturally"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The promised worst-case bounds apply only for error tolerances above a threshold whose value is not proved; if the conjectured thresholds are wrong, the paper does not actually tell the user how large the tolerance must be for the Gamma bound to hold.","fun_headline_variants_meta":{"raw":{"variants":["Gaussian trace worst tail is Gamma if thresholds hold","Extremal Gaussian trace tails are Gamma, if conjectures hold","Worst-case spectra give Gamma tails if conjectures hold","Worst tail for Gaussian trace: Gamma, conjecturally"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.002346,"raw_usage":{"total_tokens":9044,"prompt_tokens":953,"completion_tokens":8091,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":569,"completion_tokens_details":{"reasoning_tokens":8023}},"tokens_in":569,"tokens_out":8091,"duration_ms":47450,"temperature":1.0,"reasoning_tokens":8023,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:17:00.095096+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the explicit worst-case matrix $A_{\\mathrm{rel}}(\\mu)$ of (2), fix $m$, and evaluate the tail probability at $\\varepsilon = 2/(m\\mu)$; if $\\Pr(|\\mathrm{tr}_m^G(A)-\\mathrm{tr}(A)| \\ge \\varepsilon\\,\\mathrm{tr}(A))$ exceeds $\\Pr(|X-1|\\ge \\varepsilon)$ with $X\\sim \\mathrm{Gamma}(m\\mu/2,m\\mu/2)$, then Conjecture 3 is false and Theorem 6's stated range collapses. The analogous absolute test evaluates $\\varepsilon = 2\\lambda/m + \\sqrt{2\\varphi^2/m + (2\\lambda/m)^2}$ against $2\\Pr(X-\\mathbb{E}[X]\\ge \\varepsilon)$ with $X\\sim \\mathrm{Gamma}(m\\rho/2,m/(2\\lambda))$.","supporting_citations":[{"cited_title":"On randomized trace estima tes for indefinite matrices with an application to determinants","cited_arxiv_id":null,"evidence_quote":"Supplies the concentration bound (Theorem 1) and the effective-rank corollary that the paper aims to tighten."},{"cited_title":"Sz´ ekely","cited_arxiv_id":null,"evidence_quote":"Provides the majorization result for nonnegative sums of Gamma variables that Theorem 2 restates."},{"cited_title":"Sz´ ekely, and Uri M","cited_arxiv_id":null,"evidence_quote":"Extends extremal probabilities to sums of Gamma variables with arbitrary shape and scale, used for the sampling-number and infinite-division arguments."},{"cited_title":"Sz´ ekely and Nail K","cited_arxiv_id":null,"evidence_quote":"Gives extremal probabilities for Gaussian quadratic forms and the unimodality of such distributions used in the density-sign argument."},{"cited_title":"Academic Press, 1992","cited_arxiv_id":null,"evidence_quote":"Supplies the two-coordinate decomposition lemma for majorization used to reduce comparisons to pairwise transfers."},{"cited_title":"Improved variants of the hutch++ algorithm for trace estimation","cited_arxiv_id":null,"evidence_quote":"Used in the conclusion to translate the tightened bounds into sample counts for Frobenius-norm and trace estimation."}],"review_version":1}