{"id":"2021b571-b420-4555-8298-e7d5e420ffb2","arxiv_id":"1908.09598","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"First algorithms and solvability-complexity classifications for computing Lebesgue measure, capacity, and fractal dimensions of spectra of infinite-dimensional linear operators.","lead":"This paper gives the first algorithms for computing geometric features of operator spectra, such as Lebesgue measure, capacity, and fractal dimension, on infinite-dimensional Hilbert spaces. It also proves how many computational limits are needed for each problem, showing the new algorithms are optimal under any model of computation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.14 Step 5 constructs normal operators with spectra on a line: with h_k in [0,1], Leb_C(Sp(A))=0 in both cases, so the claimed Lambda1 lower bound for Lebesgue measure is not proved as written.","rationale":"The reader's verdict of CONDITIONAL is reasonable, and the information-model caveat is real but standard: the SCI lower bounds are universal only within the stated evaluation sets, exactly as Definition 5.1 makes explicit. My independent check found a more specific, load-bearing gap in the proof of Theorem 3.14. The headline optimality claim for Lebesgue measure of spectra with Lambda1 requires the lower bound {Xi_L1, Omega_N, Lambda1} not in Delta_G_3. The proof given in Step 5 constructs a normal operator whose spectrum is confined to the imaginary axis when h_k is taken dense in [0,1] as written. A line segment has zero two-dimensional Lebesgue measure, so the reduction cannot distinguish the two cases of the combinatorial problem Xi_2. This means the claimed lower bound for Omega_N, and hence the chain Omega_N subset Omega_g subset Omega_B, is not supported by the proof as written. I stress that this is not an objection to the theorem itself: the construction is very close to a correct one, and replacing h_k by a sequence dense in the unit disk should repair the argument. Because the gap is localized in a core lower-bound proof but likely fixable, the appropriate verdict remains conditional rather than accept or reject. The reader's identified weakest assumption is not the same as this concern, hence my disagreement on that point, but the final verdict is unchanged.","tokens_in":65460,"tokens_out":23607,"duration_ms":261464,"concrete_test":"Take a single finite column with finitely many 1s (so Xi_2 = 0), build the finite operator D(j) exactly as in Theorem 3.14 Step 5 with h_k in [0,1], and compute Leb_C(Sp(D(j))). Since Sp(D(j)) lies on the imaginary axis, its two-dimensional Lebesgue measure is zero, directly falsifying the claimed positive-area dichotomy. Then repeat the reduction with h_k chosen dense in the closed unit disk of C (and D(j) = direct sum_{k=1}^j h_k C(j), or the analogous normal block construction) and verify that (i) A remains normal with finite matrix entries depending on finitely many array entries, and (ii) Leb_C(Sp(A)) > 0 exactly when Xi_2({a}) = 0. If the disk version works and the [0,1] version does not, the original proof has a genuine localized gap that a revision must fix.","verdict_should_be":"UNCHANGED","load_bearing_attack":"To prove {Xi_L1, Omega_N, Lambda1} not in Delta_G_3, Step 5 of the proof of Theorem 3.14 replaces each C(j) by D(j) = direct sum_{k=1}^j i h_k C(j), with h_k dense in [0,1]. But C(j) is real symmetric (Lemma 6.4) with real spectrum contained in [-1,1]; multiplying by i h_k places every spectrum on the imaginary axis. Hence Sp(A) is contained in the imaginary segment [-i,i] up to countable sets, whose two-dimensional Lebesgue measure is zero regardless of whether the encoded array satisfies Xi_2 = 0 or Xi_2 = 1. The asserted dichotomy 'positive two-dimensional Lebesgue measure iff Xi_2 = 0' therefore fails, so the reduction to Xi_2 gives no contradiction. Since Omega_N is the smallest class among Omega_N, Omega_g, Omega_B, the claimed lower bound not in Delta_G_3 for these classes with Lambda1 is not established by the submitted proof. The same gap propagates to the inherited lower bounds in Theorem 3.15. This is a concrete proof gap in a core optimality claim, although it appears easily repairable by taking h_k dense in the unit disk or by another normal construction whose spectrum has genuinely positive area.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a systematic Solvability Complexity Index (SCI) classification for the computation of geometric features of spectra of bounded linear operators on Hilbert space. The quantities treated include the spectral radius and essential spectral radius, polynomial operator norms and logarithmic capacity, the essential numerical range, detection of spectral pollution and essential spectral gaps, the Lebesgue measure of spectra and pseudospectra, the property of having Lebesgue-null spectrum, and box-counting and Hausdorff dimensions of spectra. For each problem the paper proposes explicit towers of algorithms, often with pseudocode, and proves lower bounds by reduction to combinatorial problems that are shown to be complete at various levels of the Baire hierarchy via a new general technique (Theorem 5.19). The headline theorems are the classifications in Theorems 3.3, 3.5, 3.6, 3.10, 3.14, 3.15, 3.18 and 3.20, summarized in Table 1.","tokens_in":65644,"tokens_out":13599,"duration_ms":146141,"significance":"If the results stand, this is a substantial contribution to the foundations of computational spectral theory. The paper provides the first SCI-sharp algorithms for several longstanding geometric spectral quantities, and the new Baire-hierarchy reduction technique is a genuine methodological advance that both simplifies earlier lower-bound proofs and reaches beyond SCI level 3. The upper-bound constructions are detailed, the pseudocode is concrete, and the computational examples (almost Mathieu operator, Penrose-tile Laplacian, non-normal spectral radius, essential numerical range) illustrate that the algorithms are not merely existence proofs. The self-adjoint and diagonal-operator classifications appear carefully proved. The main caveat is a specific gap in the lower-bound proof for Lebesgue measure for general normal and general bounded operators, which propagates to several related optimality claims; this is a load-bearing issue for the advertised sharpness in those cases, although the upper bounds and the self-adjoint cases are not affected.","major_comments":[{"comment":"The claimed lower bound for Lebesgue measure for Ω = ΩB, ΩN, Ωg with the evaluation set Λ1 is not established as written. The construction replaces each C(j) by D(j) = ⊕_{k=1}^j i h_k C(j), where h_k is dense in [0,1]. Since C(j) is real symmetric with Sp(C(j)) ⊂ [-1,1] by Lemma 6.4, each i h_k C(j) has spectrum contained in the purely imaginary line segment i[-h_k,h_k]. Consequently the spectrum of the direct sum is a countable union of finite sets and has two-dimensional Lebesgue measure zero regardless of the encoded array. The asserted dichotomy 'positive two-dimensional Lebesgue measure iff Ξ̃2 = 0' therefore fails, and the reduction to the SCI = 3 combinatorial problem yields no contradiction. This invalidates the lower bound {Ξ^L_1, Ω, Λ1} ∉ Δ^G_3 for Ω = ΩB, ΩN, Ωg as written. The same gap propagates to the lower bounds of Theorem 3.15, which are derived directly from Theorem 3.14, and to the Λ1 lower bounds for ΩB, ΩN, Ωg in Theorem 3.18, which the proof says follow from the same Step-5 construction. A repair requires a genuinely two-dimensional spectral embedding, for example a normal diagonal operator whose eigenvalues accumulate on a set of positive area; replacing h_k by points in the unit disk does not suffice, since each summand still has one-dimensional spectrum.","section":"Section 8, proof of Theorem 3.14, Step 5"},{"comment":"The remark states that the Hausdorff-dimension proofs 'can be adapted with an additional limit and the use of two-dimensional covering boxes to treat the class of general bounded operators', but no proof or even sketch is provided and the details are explicitly omitted. This is an unproved classification claim. The main theorem is stated only for self-adjoint operators, so this extension is not load-bearing for the central results, but it should either be proved in an appendix or clearly marked as outside the scope of the paper.","section":"Section 3.5, remark after Theorem 3.20"}],"minor_comments":[{"comment":"The text 'easier than the general clmss ΩB' contains a typo: 'clmss' should be 'class'.","section":"Section 3.2, before Theorem 3.3"},{"comment":"The pseudocode for NullLebSpec calls LebPseudoSpec(n1, n2, f(n1), cn1, A), but the signature of LebPseudoSpec in Algorithm 11 is LebPseudoSpec(n, A, ϵ). The arguments do not match, and no value of ϵ is supplied. Also, the loop 'for j = 1,...,n1' computes the identical quantity each time, so either the loop index should affect the computation or the loop should be removed.","section":"Appendix B, Algorithm 12 (NullLebSpec)"},{"comment":"In the definition of U(n1,n2,A), the function Fn1(z) is used but the surrounding text sometimes writes Fn(z); this is understandable but should be made uniform to avoid confusion between the first and second limit parameters.","section":"Theorem 3.14 proof, Step 1"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, this is a genuinely useful paper for the SCI hierarchy and computational spectral theory: it provides the first algorithms and classifications for Lebesgue measure, capacity, and fractal dimensions of spectra, and the Baire-hierarchy connection is a real step forward for lower-bound proofs. Second, one central optimality claim has a concrete proof gap. In Step 5 of Theorem 3.14, the construction D(j) = ⨁_{k=1}^j i h_k C(j), with h_k dense in [0,1], puts every block's spectrum on the imaginary axis. The spectrum of the direct sum is then contained in i[-1,1] (up to countable sets), so its two-dimensional Lebesgue measure is zero regardless of whether the encoded array satisfies Ξ̃_2 = 0 or 1. The claimed positive-area dichotomy fails, so the reduction from Ξ̃_2 does not establish the lower bound. The same construction is reused in Theorem 3.15 and in parts of Theorem 3.18, so those lower bounds are not proved as written. The fix is straightforward: take h_k dense in the unit disk rather than [0,1]; then the union of the segments i h_k [-1,1] covers the whole disk and the dichotomy is restored. This is a repair, not a new idea, but it needs to be written into the paper.\n\nWhat is solid and genuinely new: the upper-bound algorithms for Lebesgue measure, capacity, box-counting and Hausdorff dimension are careful and appear correct; the SCI classifications for spectral radius, essential numerical range and spectral pollution are well proved; and the Baire-hierarchy tool (Theorem 5.19) is clean and simplifies earlier arguments. The paper includes pseudocode and illustrative numerical examples, though not the code or data needed for independent reproduction.\n\nMinor soft spots: the remark after Theorem 3.20 claims an extension to general bounded operators for Hausdorff dimension with details omitted, and the numerical examples are not independently reproducible as shipped. Neither affects the core theorems for the stated operator classes.\n\nThis paper deserves a serious referee. The upper-bound half stands, and the lower-bound gap is isolated, easy to state, and likely fixable in revision. I would send it out rather than desk-reject.","headline":"A substantial SCI-hierarchy paper with a real but repairable gap in the Lebesgue-measure lower-bound proof: the step-5 normal-operator construction puts all spectra on the imaginary axis, so the claimed optimality does not go through as written.","tokens_in":66222,"tokens_out":4629,"would_cite":true,"duration_ms":46229,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["47A10","46N40","47A12","47N50","81Q10","28A78","28A12"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper provides the first algorithms for computing geometric features of spectra—Lebesgue measure, capacity, box-counting and Hausdorff dimensions, spectral radii, and essential numerical ranges—and proves, via the Solvability…","keywords":["computational spectral problems","Solvability Complexity Index hierarchy","Lebesgue measure of spectra","box-counting dimension","Hausdorff dimension","spectral pollution","capacity of spectra","essential numerical range"],"falsifier":"Take the diagonal operator $D=\\mathrm{diag}(r_1,r_2,\\ldots)$ on $\\ell^2(\\mathbb{N})$ with $\\{r_n\\}$ a dense enumeration of $[0,1]$, so $Leb(Sp(D))=1$. Any algorithm that reads finitely many entries of $D$ must give the same output on $D$ as on some finite diagonal operator whose spectrum is a finite set (measure zero), so its output cannot eventually lie within $1/2$ of both answers; running the paper's LebSpec tower on this $D$ and on its finite truncations is a concrete experiment that exhibits the two-limit convergence and the failure of any one-limit method.","tokens_in":65182,"feed_emoji":"📐","tokens_out":9060,"duration_ms":87238,"temperature":0.7,"pith_summary":"The paper's central claim is that many long-unanswered \"geometric\" questions about spectra of bounded linear operators are computable, but only at a precisely calibrated cost: they need towers of algorithms with two, three, or even four nested limits, and no algorithm of the allowed type can get by with fewer. The quantities covered include the Lebesgue measure of the spectrum and pseudospectrum, whether that measure is zero, logarithmic capacity, box-counting and Hausdorff dimensions, spectral and essential spectral radii, the essential numerical range, and the decision problem of whether spectral pollution can occur in a given set. A sympathetic reader would care because these features control physically meaningful behaviour—wavepacket spreading, stability, gaps in essential spectra, and the failure of the finite-section method—and no general algorithms existed for them before. The proof combines new algorithms built on finite rectangular resolvent-norm approximations with a new lower-bound technique that equates the SCI hierarchy with the Baire hierarchy for certain combinatorial problems, so the impossibility results do not depend on a specific programming model.","feed_headline":"First algorithms compute spectra's measure and fractal dimensions","feed_subtitle":"New multi-limit towers compute these quantities and prove that no simpler algorithm can exist.","key_machinery":"The load-bearing machinery is a pair of tools. The first is the finite rectangular resolvent approximation: the function $\\gamma_n(z;A)=\\min\\{\\sigma_1((A-zI)|_{P_nH}),\\sigma_1((A^*-\\bar z I)|_{P_nH})\\}$, where $\\sigma_1$ is the smallest singular value and $P_n$ the projection onto the first $n$ basis vectors, converges uniformly on compact sets from above to the reciprocal resolvent norm $\\|R(z,A)\\|^{-1}$. All the algorithms for measure, dimension, capacity and radii work by reading these approximations on a grid and taking nested limits as the truncation width, grid spacing, and resolvent cut-off go to zero; the $\\Sigma$/ $\\Pi$ classification encodes which direction the error is controlled in. The second is a new universal lower-bound technique: for the special combinatorial problems on $\\{0,1\\}^{\\mathbb{N}}$ (deciding whether a 0-1 array has a column with infinitely many ones, and variants), the SCI hierarchy coincides exactly with the Baire hierarchy of descriptive set theory. Embedding these array problems into diagonal and block-operator spectral problems then proves that the corresponding spectral tasks cannot be solved by any general tower of lower height, regardless of the model of computation used.","core_discovery":"On the paper's own terms, the discovery is a sharp classification, not just a collection of algorithms. For general bounded operators with the basic evaluation set $\\Lambda_1$ (finitely many matrix entries per step), the Lebesgue measure of the spectrum is computable by a $\\Pi^A_3$ tower and is not computable by any $\\Delta^G_3$ tower (Theorem 3.14); the measure of pseudospectra is easier, $\\Sigma^A_2$ with $\\Lambda_1$ and $\\Sigma^A_1$ with $\\Lambda_2$ (Theorem 3.15). Deciding whether the spectrum has Lebesgue measure zero is strictly harder still, $\\Pi^A_4$ for self-adjoint operators with $\\Lambda_1$ (Theorem 3.18)—the paper's first spectral problems requiring four limits. For self-adjoint operators, box-counting dimension of the spectrum is $\\Pi^A_3$ and Hausdorff dimension is $\\Sigma^A_4$ when only $\\Lambda_1$ is available, dropping by one limit when $\\Lambda_2$ is allowed (Theorem 3.20). The paper also shows that computing the spectral radius of a general operator is exactly as hard as computing the spectrum itself ($\\Pi^A_3$), and that detecting whether spectral pollution can occur on a set is strictly harder than the spectral computation the finite-section method was designed to solve. These classifications are accompanied by explicit algorithms, pseudocode, and computational demonstrations on operators such as the almost Mathieu operator and a Laplacian on a Penrose tiling.","pith_inferences":["If the information model were enriched—for example, by allowing algorithms to query the resolvent norm directly, or to read entries selected by a non-computable rule—the classifications in this paper would not necessarily survive; the advertised universality is universality over models of computation that share the $\\Lambda_1$/ $\\Lambda_2$ evaluation sets.","Because the lower bounds rest on the equivalence with the Baire hierarchy, the same combinatorial embeddings could be applied to other high-SCI problems outside spectral theory, such as computing invariant measures, attractors, or solution manifolds of PDEs, whenever the problem can be reduced to deciding properties of infinite 0-1 arrays.","The algorithms' monotone convergence makes them suitable for rigorous computer-assisted proofs: running the $\\Pi^A_k$ towers with interval arithmetic can certify upper bounds on measures and dimensions of spectra, which is exactly the kind of certificate needed to confirm conjectures for quasicrystal or random Schrödinger operators beyond the one-dimensional almost Mathieu case.","The Penrose-tiling computations suggest a testable physical prediction: the part of the spectrum above $-3$ for the graph Laplacian on a Penrose tiling has Lebesgue measure zero and box-counting dimension near $0.8$; a future rigorous implementation of the same algorithm could turn this numerical evidence into a theorem."],"forward_implications":["Computing the spectral radius of a general bounded operator is no easier than computing the spectrum itself, contradicting the naive expectation from Gelfand's formula that one limit suffices.","For self-adjoint operators, the Lebesgue measure of the pseudospectrum can be approximated with one or two limits (depending on the evaluation set), and letting the pseudospectral radius tend to zero gives the measure of the true spectrum; deciding whether the spectrum is Lebesgue null requires up to four limits.","Box-counting dimension of self-adjoint spectra is computable with a $\\Pi^A_3$ tower, and Hausdorff dimension with a $\\Sigma^A_4$ tower, when only matrix entries are read; the extra limit reflects the countable stability of Hausdorff dimension.","Detecting a gap in the essential spectrum, equivalently deciding whether spectral pollution can occur on a given set, is strictly harder than the spectral computation itself ($\\Sigma^A_3$), so a 'failure flag' for the finite-section method cannot be produced by the same algorithm that computes the spectrum.","The new lower-bound technique extends the SCI hierarchy beyond height three; it gives the first spectral decision problems with SCI exactly four, and simplifies earlier proofs of lower bounds."],"supporting_citations":[{"why":"Supplies the SCI hierarchy definitions, the classification of spectral computation, and the towers-of-algorithms framework that this paper extends.","marker":"[20]"},{"why":"Established the SCI for computing spectra and the n-pseudospectrum approach using resolvent-norm approximation, which the new algorithms build on.","marker":"[84]"},{"why":"Provides the error-control routines for spectra and pseudospectra that are the first-level subroutine in the measure and dimension algorithms.","marker":"[51]"},{"why":"Extends the spectral algorithms to unbounded operators and provides rectangular truncation estimates used in the towers.","marker":"[49]"},{"why":"Identifies the capacity of the spectrum with an infimum over monic polynomials, the definition used here.","marker":"[80]"},{"why":"Characterizes spectral pollution via the essential numerical range, motivating the pollution-detection classifications.","marker":"[128]"},{"why":"Defines the essential numerical range for unbounded operators and characterizes it as the set of possible spectral pollution; the paper's unbounded-operator results rely on this.","marker":"[34]"},{"why":"Supplies the descriptive set theory facts used in the new lower-bound technique equating the SCI hierarchy with the Baire hierarchy for well-behaved domains.","marker":"[91]"}],"fun_headline_variants":["First algorithms compute spectra's measure, capacity, dimension","Sharp classification: spectral geometry now computable","Multi-limit towers compute spectral geometry optimally","Spectra geometry: new algorithms, optimal limits"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"All the impossibility results are proved for algorithms whose only information about an operator is finitely many matrix entries per step (or, with $\\Lambda_2$, finitely many entries of $A^*A$ and $AA^*$ as well); if a different oracle were allowed—say, direct queries to the resolvent norm—the number of required limits could drop.","fun_headline_variants_meta":{"raw":{"variants":["First algorithms compute spectra's measure, capacity, dimension","Sharp classification: spectral geometry now computable","Multi-limit towers compute spectral geometry optimally","Spectra geometry: new algorithms, optimal limits"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000959,"raw_usage":{"total_tokens":4191,"prompt_tokens":1156,"completion_tokens":3035,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":772,"completion_tokens_details":{"reasoning_tokens":2977}},"tokens_in":772,"tokens_out":3035,"duration_ms":22835,"temperature":1.0,"reasoning_tokens":2977,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:06:58.720215+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the diagonal operator $D=\\mathrm{diag}(r_1,r_2,\\ldots)$ on $\\ell^2(\\mathbb{N})$ with $\\{r_n\\}$ a dense enumeration of $[0,1]$, so $Leb(Sp(D))=1$. Any algorithm that reads finitely many entries of $D$ must give the same output on $D$ as on some finite diagonal operator whose spectrum is a finite set (measure zero), so its output cannot eventually lie within $1/2$ of both answers; running the paper's LebSpec tower on this $D$ and on its finite truncations is a concrete experiment that exhibits the two-limit convergence and the failure of any one-limit method.","supporting_citations":[{"cited_title":"The foundations of spectral computations via the Solvability Complexity Index hierarchy","cited_arxiv_id":"1908.09592","evidence_quote":"Extends the spectral algorithms to unbounded operators and provides rectangular truncation estimates used in the towers."},{"cited_title":"Studia Mathematica 65(1), 21–29 (1979)","cited_arxiv_id":null,"evidence_quote":"Characterizes spectral pollution via the essential numerical range, motivating the pollution-detection classifications."}],"review_version":1}