# Category Archives: Programming

## What do We Have to Know About a Function in Order to Compute its Definite Integral?

Suppose that $f$ is a continuous function from $\lbrack 0,1\rbrack$ to $\lbrack 0,1\rbrack$ and that we have a program which computes it. (Ignore for now exactly what it means to “compute” a real-valued function of the reals. Suffice it to say that almost every natural continuous function you come across is computable). If we want to compute $\int_{0}^1 f(x)\,dx$, say to within an accuracy of $0.001$, how would we do it, and would we need any further information about $f$ in order to do it?

The obvious thing to do is to compute a Riemann sum $R(f,n)=\sum_{i=0}^{n-1} (1/n)\cdot f(i/n)$ for some large $n$. However, this could be arbitrarily far from the true value of $\int_0^1 f(x)\,dx$. For example, $f(i/n)$ might be 0 for all $0 \leq i \leq n-1$, but $f$ might curve sharply up in between each $i/n$ and $(i+1)/n$ so that its definite integral is arbitrarily close to 1.

However, since $f$ is continuous on $\lbrack 0,1\rbrack$, it is uniformly continuous. This means that for all $\epsilon > 0$ there is a $\delta > 0$ such that whenever $|x - y| < \delta$, $|f(x) - f(y)| < \epsilon$. If we could compute a function $\delta(\epsilon)$ such for all $\epsilon > 0$, whenever $|x - y| < \delta(\epsilon)$, $|f(x) - f(y)| < \epsilon$, then we could compute the definite integral of $f$ with arbitrary accuracy: If we want to know $\int_0^1 f(x)\, dx$ to within 0.001, then choose $n$ so that $1/n < \delta(0.001)$ and we can take $R(f,n)$, since $|R(f,n) - \int_0^1 f(x)\,dx| < 0.001$.

So, one answer to the question “What extra information do we need in order to compute $\int_0^1 f(x)\,dx$?” is: a function $\delta(\epsilon)$ witnessing $f$‘s uniform continuity.

In 1998, Alex Simpson showed, building on ideas of Ulrich Berger and others, that another answer is: Nothing!