Christopher Sorg

Christopher Sorg

We study endpoint Koopman spectral computation from the viewpoint of the Solvability Complexity Index (SCI). Let \((\mathcal X,d)\) be a compact metric space with finite Borel measure \(ω\), and let \(\mathcal K_F\) be the Koopman operator associated with a continuous nonsingular map \(F:\mathcal X\to\mathcal X\). First, on \(L^1(\mathcal X,ω)\), we record the endpoint residual upper-bound in the target-split form. The regularized compact fixed-\(\varepsilon\) target $R_{\mathrm{ap},\varepsilon}(\mathcal K_F)$ is separated from the closed fixed-\(\varepsilon\) target $C_{\mathrm{ap},\varepsilon}(\mathcal K_F)$ and from the exact approximate point spectrum $σ_{\mathrm{ap}}(\mathcal K_F).$ This endpoint statement uses the same point-evaluation plus fixed-quadrature information model as the \(1<p<\infty\) residual theory. Second, we isolate two obstructions at the nonseparable endpoint \(L^\infty\). Fixed quadrature schemes do not discretize the full \(L^\infty\) unit sphere, and even inside measure-preserving Cantor homeomorphisms the map $F\mapsto σ_{\mathrm{ap}}(\mathcal K_F:L^\infty\to L^\infty)$ is maximally discontinuous in Hausdorff distance under arbitrarily small uniform perturbations of \(F\). We also show that finite-period Silver-tree block constructions cannot yield analytic hardness for the \(L^\infty\) approximate point spectrum: for a fixed non-torsion \(z_0\in\mathbb T\), the condition $z_0\inσ_{\mathrm{ap}}(\mathcal K_{F}:L^\infty\to L^\infty)$ collapses to a Borel unbounded-period condition. In addition, fixed \(L^\infty\) point-eigenvalue membership is Borel in the measure-preserving continuous class, so one fixed eigenvalue cannot encode a non-Borel tree predicate. Third, we construct Koopman point-spectrum calibration families on the Cantor space.

Vasco Brattka, Christopher Sorg

Computational properties of the Hahn-Banach theorem have been studied in computable, constructive and reverse mathematics and in all these approaches the theorem is equivalent to weak Kőnig's lemma. Gherardi and Marcone proved that this is also true in the uniform sense of Weihrauch complexity. However, their result requires the underlying space to be variable. We prove that the Hahn-Banach theorem attains its full complexity already for the Banach space $\ell^1$. We also prove that the one-step Hahn-Banach theorem for this space is Weihrauch equivalent to the intermediate value theorem. This also yields a new and very simple proof of the reduction of the Hahn-Banach theorem to weak Kőnig's lemma using infinite products. Finally, we show that the Hahn-Banach theorem for $\ell^1$ in the two-dimensional case is Weihrauch equivalent to the lesser limited principle of omniscience.

Christopher Sorg

We study residual computation of approximate point spectral sets of bounded Koopman operators $\mathcal K_F$ on $L^p(\mathcal X,ω)$, $1<p<\infty$, where $\mathcal X$ is a compact metric space and $ω$ is a finite Borel measure. The input is the underlying map $F : \mathcal X \to \mathcal X$, accessed through point evaluations, and the output metric is the Hausdorff metric on non-empty compact subsets of $\mathbb C$. For a bounded operator $T$, we distinguish the regularized approximate point $\varepsilon$-pseudospectrum $R_{\mathrm{ap},\varepsilon}(T)$ from the closed approximate point $\varepsilon$-pseudospectrum $C_{\mathrm{ap},\varepsilon}(T)$. The latter is the direct closed lower-norm analogue of the approximate point $\varepsilon$-pseudospectrum used in the $L^2$ Koopman SCI theory. Using continuous finite-dimensional dictionaries and tagged quadrature residuals, we prove SCI upper bounds for $R_{\mathrm{ap},\varepsilon}(T)$, $C_{\mathrm{ap},\varepsilon}(T)$, and $σ_{\mathrm{ap}}$ on four natural classes of maps: continuous nonsingular maps, maps with a prescribed modulus of continuity, measure-preserving maps, and maps satisfying both measure preservation and a prescribed modulus.

Christopher Sorg

We study how exact Solvability Complexity Index (SCI) statements should be formulated for families of computational problems rather than for single problems. While the equality \(\operatorname{SCI}_G (\mathcal P)=k\) is unambiguous for an individual computational problem \(\mathcal P\), the family setting requires one to distinguish family-pointwise exactness, witness-space sharpness, and worst-case exactness. We formalize this trichotomy, prove that witness-space sharpness coincides with worst-case exactness but is, in general, strictly weaker than family-pointwise exactness, and show that certain Koopman-operator classification results are sharp only in this worst-case sense. We then establish two positive upgrade theorems: an abstract pullback principle and a concrete finite-query criterion guaranteeing that witness-space sharpness upgrades to family-pointwise exactness. Next, we introduce a decoder-regular finite-query transport preorder on SCI computational problems, prove that it is a preorder, derive a transport-saturation sufficient criterion extending the principal-source package, and show that the associated transport degrees need not form a lattice in full generality. We analyze the natural decoder classes \(\mathscr R_{\mathrm{cont}}\) and \(\mathscr R_{\mathrm{Bor}}\): on the full class the corresponding quotients are not upper semilattices, while on the nondegenerate subclass the preorder is upward and downward directed. Finally, we exhibit two natural positive families realizing the principal transport mechanism: exact integration on compact intervals and a fixed-window spectral decision family obtained by block-diagonal stabilization.

Christopher Sorg

The Solvability Complexity Index (SCI) provides an abstract notion of computing a target map $Ξ$ from finitely many oracle evaluations $Λ\subseteq \mathbb{C}$ via finite-height towers of pointwise limits. We first give a foundational analysis of what this extensional framework does and does not determine. We show that the SCI separation consistency is equivalent to a factorization of $Ξ$ through the full evaluation table, and we isolate the minimal logical role of $Λ$ as an information interface. To connect the SCI to Type-2 computability and Weihrauch reducibility, we give an effective enrichment for countable $Λ$ by viewing the evaluation table image $I_Λ\subseteq\mathbb{C}^{\mathbb{N}}$ as a represented space and factoring $Ξ$ as $\widehatΞ$. We then define the Weihrauch-SCI rank of a problem as the least number of iterated limit-oracles needed to compute it in the Weihrauch sense, i.e.\ the least $k$ such that $\widehatΞ\le_{W}\lim^{(k)}$, and prove well-posedness and representation invariance of this rank. A central negative result is that the unrestricted type-$G$ SCI model (arbitrary post-processing of finite oracle transcripts) is generally not comparable to Weihrauch/Type-2 complexity: finite-query factorizations collapse type-$G$ height, and analytic (non-Borel) decision problems yield examples with $\mathrm{SCI}_{G}=0$ but infinite Weihrauch-SCI rank. To recover a robust bridge, we introduce an intermediate SCI hierarchy by restricting the admissible base-level post-processing to regularity classes (continuous/Borel/Baire) and, optionally, to fixed-query versus adaptive-query policies. We prove that these restrictions form genuine hierarchies, and we establish comparison theorems showing what each restriction logically enforces (e.g.\ Borel towers compute only Borel targets; continuous-base towers yield finite Baire class).