{"id":"6e063ac6-2209-49cb-98b0-acbfd2754472","arxiv_id":"1908.09592","paper_version":4,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Sharp Solvability Complexity Index classifications are established for spectra of unbounded differential and graph operators, the spectral gap problem, and discrete spectra, with constructive algorithms realizing the optimal levels.","lead":"This paper proves sharp limits on which infinite-dimensional spectral problems can be solved by algorithms, and provides new error-controlled algorithms for spectra of differential operators on unbounded domains and operators on graphs. A generalist should read it because it turns folklore about non-computable spectra into precise classification levels with consequences for computer-assisted proofs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.15's sharp /∈ Δ^G_3 lower bound for discrete spectra is outsourced to companion paper [41], so that part of the central classification is not self-contained.","rationale":"The reader accepted with moderate confidence and identified the known resolvent bounds as the weakest assumption. That assumption is explicit in the theorem statements and affects all main results, but it is a defined input rather than an unproved step. The more concrete unproved dependency is Theorem 3.15's lower bound, which the manuscript itself flags by citing [41]. The completeness rule requires flagging omitted proofs. The concern is limited in scope: Theorems 3.3, 3.5, 3.8, 3.9, 3.11, and 3.13 are proved in the text, so the paper's core PDE and graph classifications survive. However, the advertised discrete-spectrum classification without bounded dispersion is not self-contained, so overall acceptance should be conditional on the companion result being verified or included.","tokens_in":62472,"tokens_out":20355,"duration_ms":212699,"concrete_test":"Verify the companion proof: inspect [41] for a complete, self-contained proof that the stated 0-1 decision problem has SCI^G=3, and check that the reduction in Section 8, Step 1 of this paper is a faithful mapping to {Ξ^d_1,Ω^d_1} and {Ξ^d_2,Ω^d_2} using only information available in those classes. If [41] contains the proof and the reduction is exact, the concern settles; if the companion result is absent, mis-stated, or the reduction uses extra information, Theorem 3.15's lower bound should be withdrawn or re-proved.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"The paper's Table 1 and abstract advertise sharp classifications for computing discrete spectra and deciding non-emptiness without bounded dispersion: {Ξ^d_1,Ω^d_1}∈Σ^A_3 but not Δ^G_3, and {Ξ^d_2,Ω^d_2}∈Σ^A_3 but not Δ^G_3. The positive (Σ^A_3) towers are constructed in Section 8. However, the negative half is not proved in this manuscript. The proof of Theorem 3.15, Step 1, says: 'For this proof we shall use one of the decision problems in [41] that were proven to have SCI^G = 3.' Reference [41] is the companion preprint 'The foundations of spectral computations ... Part II' (arXiv:1908.09598). The decision problem ('does the 0-1 matrix have only finitely many columns with finitely many non-zero entries?') and its SCI^G=3 classification are not restated or proven here. Since Theorem 3.15's lower bound is exactly what makes the classification sharp, the manuscript's claim for discrete spectra without dispersion is conditional on an external, self-cited preprint. The primary PDE classifications (Theorems 3.3 and 3.5) are self-contained and are not affected by this concern.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops the Solvability Complexity Index (SCI) hierarchy for spectral problems and establishes sharp classifications with constructive algorithms for several central problems: computing spectra and pseudospectra of differential operators on unbounded domains (Theorems 3.3 and 3.5), unbounded operators on graphs and separable Hilbert spaces (Theorem 3.8), the spectral gap and spectral classification problems (Theorem 3.11), and discrete spectra, multiplicities, and eigenspaces (Theorems 3.13–3.15). Positive results are proved via explicit towers of arithmetic algorithms, with pseudocode in Appendix A; negative results show that general one- or two-limit algorithms cannot provide the corresponding error control. The paper also supplies numerical examples illustrating the algorithms on anharmonic oscillators, PT-symmetric operators, and the Almost Mathieu operator. The primary PDE classifications are self-contained, while the sharpness of the discrete-spectrum results without dispersion relies on a companion preprint.","tokens_in":62725,"tokens_out":10916,"duration_ms":102035,"significance":"If the results hold, this paper makes a major contribution to the foundations of computational spectral theory. It answers long-standing open questions by showing that spectra of large classes of differential operators on unbounded domains can be computed with certified error control from point samples of coefficients, and it provides sharp SCI classifications for spectral gap, classification, and discrete-spectrum problems. The constructive nature of the proofs is a notable strength: the paper supplies concrete algorithms and pseudocode that could be used in computer-assisted proofs, and the numerical examples demonstrate practical utility. The main caveat is that the sharp /∈ Δ^G_3 lower bounds in Theorem 3.15 are not proved in this manuscript but are imported from the self-cited companion paper [41]; the primary PDE results and the bounded-dispersion discrete-spectrum results are, however, self-contained. Overall, the paper is a substantial advance in the classification program, provided the external dependency is resolved or explicitly qualified.","major_comments":[{"comment":"The sharp lower bounds in Theorem 3.15 ({Ξ^d_1, Ω^d_1} ∉ Δ^G_3 and {Ξ^d_2, Ω^d_2} ∉ Δ^G_3) are not proven in this manuscript. Step 1 of the proof states: \"For this proof we shall use one of the decision problems in [41] that were proven to have SCI^G = 3,\" and the referenced decision problem and its classification are neither restated nor proved here. Since these lower bounds are exactly what makes the classification sharp, the advertised results for discrete spectra without bounded dispersion in Table 1 and the abstract are conditional on the companion preprint arXiv:1908.09598. The positive Σ^A_3 towers are constructed in the paper, but the negative half is load-bearing. I recommend either including a proof of the needed SCI^G = 3 decision problem in this paper (or an appendix), or, if Part II is published, citing the published version and explicitly marking the lower bound as proven there.","section":"Section 8, proof of Theorem 3.15, Step 1"}],"minor_comments":[{"comment":"The evaluation set Λ for the differential-operator problems should be defined explicitly (e.g., all point evaluations of the coefficients and their adjoints) so that the separation condition in Definition 2.1 is satisfied; a reader cannot otherwise rule out two different coefficient functions agreeing on the oracle.","section":"Section 3.1.1"},{"comment":"In the Π^G_1 lower-bound argument, the phrase \"choose n large such that Γ_n(T0) produces the guarantee Sp(T0)∩B_{1/4}(0)^c = ∅\" is insufficient on its own, since this statement is trivially true for T0. One should instead use the convergence of Γ_n(T0) to {0} together with d(X_n, Γ_n) ≤ 2^{-n} to show that the guaranteed set X_n is contained in B_{1/4}(0); the argument is repairable but should be stated precisely.","section":"Section 7.2, proof of Theorem 3.3"},{"comment":"The definition of E_n(z) appears to contain a typo: \"E_n(z) = CompInvg(n, γ_n(z,A), g^{-1}_{⌈|z|⌉})\" should likely be \"E_n(z) = CompInvg(n, γ_n(z,A), g_{⌈|z|⌉})\" to match the displayed formula in Remark 6.11.","section":"Section 6, proof of Theorem 3.8"},{"comment":"The numerical examples would be more reproducible if the code or a link to code were provided, though this does not affect the mathematical content.","section":"Section 10"},{"comment":"The list of \"Recent results on computing spectra\" contains duplicated numbering items (ii) appearing three times; this is an editorial artifact and should be corrected.","section":"Section 4"}],"recommendation":"major_revision","confidential_remarks":"The paper relies on the companion preprint [41] for a central lower bound in Theorem 3.15. The authors should clarify the publication status of Part II; if the two parts are intended as a single body of work, the editor may consider whether the conditional statement is acceptable, but the advertising of a sharp classification in the abstract makes the dependency worthy of explicit qualification. Otherwise, the paper is a strong contribution and the primary PDE classifications are self-contained."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nYou should know two things about this paper. First, the core classification results hold up: spectra and pseudospectra of large classes of PDEs on unbounded domains are shown to be in Sigma^A_1 (convergent one-limit algorithms with error control) and not in Delta^G_1, and the same sharpness is proved for graph operators, the spectral gap problem, and spectral classification at the bottom of the spectrum. The proofs are constructive and detailed, with pseudocode and worked numerical examples. This is a real step forward, not just a repackaging of the framework.\n\nSecond, the advertised sharp classification for discrete spectra without bounded dispersion (Theorem 3.15, entries in Table 1) is only half-proved here. The Sigma^A_3 towers are constructed in Section 8, but the /in Delta^G_3 lower bound is lifted from the companion preprint [41], Part II, without reproducing the decision problem or its proof. So that part of the abstract is conditional on an external self-cited manuscript. If the companion is published this is fine, but in the present form, the sharpness claim for that specific problem should be flagged as such. The PDE theorems (3.3, 3.5) and spectral gap theorem (3.11) are self-contained; this is a localized caveat, not a load-bearing flaw.\n\nThe input assumptions are strong - you need known resolvent bounds (3.4) and norm bounds on coefficients - but they are stated clearly and are the price of guaranteed error control. Remark 3.2 honestly notes that without resolvent control the problem is not even Delta^G_2. No code is shipped, but the pseudocode is concrete and the numerical examples report interval-arithmetic certification; for a theory paper I don't consider that a deficiency. The citation pattern is heavily self-referential, but the authors are building their own program and the cited results (essential-spectrum tower, SCI framework) are real; I don't see circularity in the main classifications.\n\nWho should read it: anyone working on computational spectral theory, especially people who want rigorous computer-assisted proofs for spectra. It deserves a serious referee. My recommendation: send to review, and ask the authors to either prove Theorem 3.15's lower bound locally or restate it as conditional on the companion, with the dependence explicit in the abstract and Table 1.","headline":"Strong, mostly self-contained SCI classifications for spectra of PDEs on unbounded domains and the spectral gap; one caveat: the no-dispersion discrete-spectrum lower bound is imported from the companion Part II.","tokens_in":63188,"tokens_out":4549,"would_cite":true,"duration_ms":40955,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["46N40","47A10","35P15","65L15","65N25"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper fixes the exact limits of spectral computation: spectra of differential operators on unbounded domains are computable with certified error from point samples of coefficients, while the spectral gap problem provably is not.","keywords":["Solvability Complexity Index hierarchy","computational spectral theory","spectra of differential operators on unbounded domains","certified error control","spectral gap problem","discrete spectrum and multiplicities","computer-assisted proofs","pseudospectra"],"falsifier":"Run the published routine CompSpecUB with interval arithmetic on a concrete operator in $\\Omega^1_{TV}$ with a known spectrum, such as $-d^2/dx^2 + x^2 + \\cos(x)$ on $L^2(\\mathbb{R})$ in the Hermite basis, and compare every certified distance $E_n(z)$ against the true distance $\\operatorname{dist}(z,\\operatorname{Sp}(T))$: one output whose certified bound is smaller than the true distance refutes the $\\Sigma^A_1$ claim. For the negative classifications, the decisive test is structural: take two diagonal self-adjoint operators that agree on their first $N$ diagonal entries but whose spectra are separated by more than $2^{-N}$; the lower-bound proofs assert that any one-limit algorithm reading only finitely many evaluations must answer identically on both, so exhibiting a tower that provably separates them refutes the $\\notin \\Delta^G_2$ results.","tokens_in":62293,"feed_emoji":"🧮","tokens_out":18384,"duration_ms":145642,"temperature":0.7,"pith_summary":"This paper fixes, for the first time in full generality, where the foundational problems of computational spectral theory sit in the Solvability Complexity Index hierarchy, the classification of computational problems by how many limits an algorithm needs. Its central positive claim is that spectra and pseudospectra of large classes of differential operators on unbounded domains, read from point samples (or power series) of their coefficients, can be computed with certified error control by arithmetic algorithms (class $\\Sigma^A_1$), while no algorithm of any computation model can achieve that with a single limit and guaranteed accuracy (class $\\Delta^G_1$). The same sharp two-sided classification is proved for operators on graphs, and for the discrete problems the paper shows that testing whether a compact set meets the spectrum is $\\Pi^A_2$ but not $\\Delta^G_2$, that the spectral gap problem and the bottom-of-the-spectrum classification are $\\Sigma^A_2$ and $\\Pi^A_2$ respectively but not $\\Delta^G_2$, and that computing discrete spectra and multiplicities costs two limits (three without dispersion information). Because $\\Sigma^A_1$ algorithms never output points outside the true spectrum beyond a certified error, the positive results make these spectral computations admissible as rigorous computer-assisted proofs, whereas the negative results rule out computer-assisted proofs for the spectral gap problem as a general method.","feed_headline":"Spectra on unbounded domains now come with certified error","feed_subtitle":"For differential and graph operators, every output point now carries a certified distance to the true spectrum.","key_machinery":"The load-bearing identity is $\\gamma(z,A) = \\min\\{\\sigma_1(A-zI), \\sigma_1(A^*-\\bar z I)\\} = \\|R(z,A)\\|^{-1}$ (Lemma 6.4), which turns the resolvent norm—the quantity governing the spectrum—into a smallest singular value computable with finitely many arithmetic operations and comparisons. The algorithms form rectangular truncations $P_{f(n)}(A-zI)P_n$, using the known off-diagonal decay (bounded dispersion, $D_{f,n}(A) \\le c_n$) to bound the truncation error, and extract singular values through positive-definiteness tests on $LDL^*$ decompositions (Sylvester's law of inertia). Certification of each output point is delivered by the input family $\\{g_m\\}$ of resolvent-growth bounds, $g_m(\\operatorname{dist}(z,\\operatorname{Sp}(A))) \\le \\|R(z,A)\\|^{-1}$ on $B_m(0)$, through the inversion routine $\\mathrm{CompInvg}$: it converts a computed lower bound on $\\|R(z,A)\\|^{-1}$ into an upper bound on the distance from $z$ to the spectrum. For differential operators the Hermite-function basis converts coefficient functions into matrix elements, computed from point samples by quasi-Monte Carlo quadrature (Halton sequences with the Koksma–Hlawka inequality), exploiting the Banach-algebra property of the total-variation norm; the negative results are forced by diagonal-operator constructions in which any algorithm reading finitely many matrix entries cannot distinguish operators with different spectra.","core_discovery":"The discovery is a sharp classification of spectral computational problems, with constructive algorithms realizing every positive result. For the classes $\\Omega^1_{TV}$ and $\\Omega^1_{AN}$ of differential operators on $L^2(\\mathbb{R}^d)$ with coefficients of bounded total variation (resp. analytic coefficients) and known resolvent growth, the maps $T \\mapsto \\operatorname{Sp}(T)$ and $T \\mapsto \\operatorname{Sp}_\\epsilon(T)$ into the Attouch–Wets metric space (a metric on closed subsets measuring agreement on every bounded set) lie in $\\Sigma^A_1$ yet not in $\\Delta^G_1$ (Theorems 3.3 and 3.5). Arithmetic algorithms converge to the true set while certifying, for each output point, a distance to it, and no general algorithm can do the same with one limit. Theorem 3.8 transfers the $\\Sigma^A_1$ classification to spectra and pseudospectra of possibly unbounded operators on graphs; Theorem 3.9 classifies the intersection decision problems as $\\Pi^A_2$ but not $\\Delta^G_2$; and Theorem 3.11 classifies the spectral gap problem as $\\Sigma^A_2$ but not $\\Delta^G_2$, even for diagonal operators, with the four-case spectral classification at the bottom of the spectrum in $\\Pi^A_2$ but not $\\Delta^G_2$. Theorems 3.13 and 3.15 place computing the discrete spectrum, its non-emptiness, and eigenvalue multiplicities at $\\Sigma^A_2$ (resp. $\\Sigma^A_3$ without bounded dispersion), with every inclusion realized by an explicit routine given as pseudocode.","pith_inferences":["The split between $\\Sigma^A_1$ (known coefficient and resolvent bounds) and $\\Delta^A_2$ (only relative bounds) suggests a transferable principle for other inverse problems: supplying norm bounds converts convergent-but-uncontrolled numerics into certified numerics; testing this on resonance computations or spectral measure approximation would be a direct extension.","The $g_m$ resolvent assumption is the practical bottleneck for non-self-adjoint problems, since for self-adjoint operators $g_m(x)=x$ is automatic; a natural next step is to develop certified algorithms that learn resolvent-growth functions adaptively during the computation rather than requiring them as input.","The decision classifications (spectrum intersecting a compact set, spectral gap) delineate exactly which spectral statements can be fed into automated theorem provers; one could build a formal-proof pipeline that translates a $\\Sigma^A_1$ run's certificate into a machine-checkable lemma about spectral inclusion or exclusion.","The rectangular truncation $P_{f(n)}(A-zI)P_n$ with bounded-dispersion $f$, rather than square truncations, is a reusable algorithmic idea likely to benefit other infinite-dimensional numerical problems such as matrix functions, invariant subspaces, or Koopman-operator approximations on unbounded state spaces."],"forward_implications":["The $\\Sigma^A_1$ inclusions for $\\Omega^1_{TV}$ and $\\Omega^1_{AN}$ give the first general guarantee that spectra of differential operators on unbounded domains can be computed from coefficient samples soundly enough for computer-assisted proofs: output is never outside the true spectrum by more than a certified, user-shrinkable error.","The $\\notin \\Delta^G_2$ classification of the spectral gap problem for diagonal self-adjoint operators means no algorithm on any computational model can return a verifiable yes/no answer to the gap question, so computer-assisted proofs of gap or gaplessness for these classes are ruled out as a general method.","Discrete spectra are computable by towers whose first limit lies inside the true discrete spectrum, so eigenvalues below the essential spectrum can be isolated and approximated with multiplicities and approximate eigenvectors carrying explicit bounds, even while the full spectrum remains two limits away.","Standard finite-section discretization is provably suboptimal for these problems: it gives at best $\\Delta^A_2$ without certified error, and the paper's computational examples show it producing spectral pollution that the new rectangular-truncation algorithms avoid.","The same classifications extend to general separable Hilbert spaces once a basis is chosen and bounded dispersion is known (Remark 10.1), making the algorithms applicable to Schrödinger, Dirac, and Jacobi operators on graphs and lattices."],"supporting_citations":[{"why":"Supplies the SCI hierarchy, towers of algorithms, and the essential-spectrum tower that the discrete-spectrum, multiplicity, and classification algorithms build on.","marker":"[8]"},{"why":"Foundational classification of spectral problems and n-pseudospectra in the SCI hierarchy; provides the definitional basis for the paper's one-limit classifications.","marker":"[73]"},{"why":"Prior certified-error-control algorithm for spectra of discrete Schrödinger operators that the differential-operator and graph theorems extend to new classes.","marker":"[43]"},{"why":"Provides the Halton sequences, star discrepancy bounds, and Koksma–Hlawka inequality used to convert point samples of total-variation-bounded coefficients into rigorously approximated matrix elements.","marker":"[85]"},{"why":"Establishes the Banach-algebra property of the total-variation norm used to control products of coefficients and Hermite basis functions.","marker":"[16]"},{"why":"Defines the arithmetic (BSS) model of computation that gives meaning to the class $\\Sigma^A_1$ and makes the $\\notin \\Delta^G_1$ lower bounds universal across models.","marker":"[14]"},{"why":"Benchmark undecidability result for the spectral gap in the thermodynamic limit, which Theorem 3.11's classification extends to infinite-dimensional diagonal operators.","marker":"[44]"},{"why":"Supplies the height-three decision problem used in the proof of Theorem 3.15 to show that computing discrete spectra without dispersion information is not in $\\Delta^G_3$.","marker":"[41]"}],"fun_headline_variants":["Sharp hierarchy settles spectral computability questions","Certified spectra from new constructive algorithms","Open spectral problems solved, others proven impossible","Error control for spectra, even on unbounded domains","Definitive algorithm hierarchy for spectral problems"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The certified spectrum algorithms work only when the user hands the algorithm a known family of functions controlling how large the resolvent can grow away from the spectrum, together with growth bounds on the operator's coefficients; those functions and bounds always exist when the spectrum is non-empty, but as input information they are indispensable, and without them the problem is not even solvable with two limits and error control.","fun_headline_variants_meta":{"raw":{"variants":["Sharp hierarchy settles spectral computability questions","Certified spectra from new constructive algorithms","Open spectral problems solved, others proven impossible","Error control for spectra, even on unbounded domains","Definitive algorithm hierarchy for spectral problems"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001755,"raw_usage":{"total_tokens":7053,"prompt_tokens":1192,"completion_tokens":5861,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":808,"completion_tokens_details":{"reasoning_tokens":5795}},"tokens_in":808,"tokens_out":5861,"duration_ms":37288,"temperature":1.0,"reasoning_tokens":5795,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:07:07.317362+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the published routine CompSpecUB with interval arithmetic on a concrete operator in $\\Omega^1_{TV}$ with a known spectrum, such as $-d^2/dx^2 + x^2 + \\cos(x)$ on $L^2(\\mathbb{R})$ in the Hermite basis, and compare every certified distance $E_n(z)$ against the true distance $\\operatorname{dist}(z,\\operatorname{Sp}(T))$: one output whose certified bound is smaller than the true distance refutes the $\\Sigma^A_1$ claim. For the negative classifications, the decisive test is structural: take two diagonal self-adjoint operators that agree on their first $N$ diagonal entries but whose spectra are separated by more than $2^{-N}$; the lower-bound proofs assert that any one-limit algorithm reading only finitely many evaluations must answer identically on both, so exhibiting a tower that provably separates them refutes the $\\notin \\Delta^G_2$ results.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Foundational classification of spectral problems and n-pseudospectra in the SCI hierarchy; provides the definitional basis for the paper's one-limit classifications."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Prior certified-error-control algorithm for spectra of discrete Schrödinger operators that the differential-operator and graph theorems extend to new classes."},{"cited_title":"Niederreiter","cited_arxiv_id":null,"evidence_quote":"Provides the Halton sequences, star discrepancy bounds, and Koksma–Hlawka inequality used to convert point samples of total-variation-bounded coefficients into rigorously approximated matrix elements."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Benchmark undecidability result for the spectral gap in the thermodynamic limit, which Theorem 3.11's classification extends to infinite-dimensional diagonal operators."},{"cited_title":"On the computation of geometric features of spectra of linear operators on Hilbert spaces","cited_arxiv_id":"1908.09598","evidence_quote":"Supplies the height-three decision problem used in the proof of Theorem 3.15 to show that computing discrete spectra without dispersion information is not in $\\Delta^G_3$."}],"review_version":1}