Partial computability results on integrals over open intervals

Question

It's well known in Type 2 Effectivity that integration over a compact interval is computable. So what about integration over an open interval? What rigorous computability results exist?

My thoughts were that, morally, that should also be computable to some degree. The reason is because it seems that it's often easy to apply a Direct Comparison Test or a Dirichlet Test and then conclude convergence from that. For instance, the integral $\Gamma(4)=\int_{0}^\infty x^3 e^{-x}\,dx$ can easily be compared to the convergent integral $\int_{0}^\infty \frac{dx}{1+x^2} = \pi/2$ which dominates it in the tails. The thing about convergence tests in general is that they are constructive, so they actually provide a way of numerically evaluating such integrals and series.

A possible approach to automatically computing $\int_{0}^\infty f(x)\,dx$ would be to figure out a $g(x)$ such that $f(x) \in O(g(x))$ and $\int_{0}^\infty g(x)\,dx$ exists.

Additionally, there are sets of function like the Schwartz functions that look especially "integrable". Maybe these are the functions for which integration can be done efficiently.

Answer 1

Suppose $f$ is Riemann-integrable on every closed interval $[a,b]$.

Proposition: $\int_0^\infty f(x) \, dx$ exists, if and only if, for every $\epsilon > 0$ there exists $b \geq 0$ such that for all $c \geq b$, $\left|\int_b^c f(x) \, dx \right| < \epsilon$.

Proof. Let us write $I(a,b) = \int_a^b f(x) \, dx$ because it's annoying to write lots of LaTeX code.

Suppose $I(0, \infty)$ exists, i.e., the limit $\lim_{b \to \infty} I(0,b)$ exists. Notice that then $I(x, \infty)$ exits for all $x \geq 0$. Consider any $\epsilon > 0$. There is $b \geq 0$ such that, for all $c \geq b$, we have $|I(0,\infty) - I(0,c)| < \epsilon/2$. Now it follows that $|I(b,c)| = |I(b,\infty) - I(c,\infty)| \leq |I(0,\infty) - I(b, \infty)| + |I(0,\infty) - I(c,\infty)| < \epsilon$.

For the converse, consider an arbitrary $\epsilon > 0$. By assumption there is $b > 0$ such that for all $c \geq b$ we have $|I(b,c)| < \epsilon/2$. Thus, for all $d \geq c \geq b$ we have $|I(0,c) - I(0,d)| \leq |I(0,c) - I(0,b)| + |I(0,d) - I(0,b)| = |I(b,c)| + |I(b,d)| < \epsilon$. We have established that the map $b \mapsto I(0,b)$ satisfies the Cauchy condition at $b \mapsto \infty$, therefore the desired limit $I(0, \infty)$ exists. $\Box$

The previous proof is constructive. Therefore, by interpreting above in the realizability model of Type Two Effectivty (the Kleene-Vesley topos), we may conclude that in TTE the represented space of functions which are Riemann-integrable on $[0,\infty]$ is computably isomorphic to the represented space of functions $f : [0,\infty) \to \mathbb{R}$, which are realized by a pair $\langle \alpha, \beta\rangle \in \mathbb{N}^\mathbb{N} \times \mathbb{N}^\mathbb{N}$ such that:

• $\alpha$ realizes $f$ (as a function that is Riemann-integrable on every closed interval, but in TTE they all are, so $\alpha$ just realizes $f$ as a map),
• $\beta$ realizes $\forall k \in \mathbb{N} . \exists m \in \mathbb{N} . \forall c \geq m . |I(m,c)| < 2^{-k}$. Concretely $\beta$ is a sequence such that, for all $k \in \mathbb{N}$ and all $c \geq \beta_k$ we have $|I(\beta_k, c)| < 2^{-k}$.

If you do not like the above representation, you are free to massage it into some other form that is computably isomorphic to it. However, in view of the above proposition, you won't be able to considerably cut down on the computational content of the realizer $\beta$.