Are there "one way" integrals?

Question

If we suppose that we can start with any function we like, can we work "backwards" and differentiate the function to create an integral that is hard to solve?

To define the question better, let's say we start with a function of our choosing, $f(x)$. We can then differentiate the function with respect to $x$ do get $g(x)$: $$g(x) = f'(x)$$

This, in turn, implies, under appropriate conditions, that the integral of $g(x)$ is $f(x)$: $$\int_a^b { g(x) dx } = [f(x)]_a^b$$

I'm wondering what conditions are appropriate to allow one to easily get a $g(x)$ and $f(x)$ that assure that $f(x)$ can't be easily found from $g(x)$.

SUMMARY OF THE QUESTION

Can we get a function, $g(x)$, that is hard to integrate, yet we know the solution to? It's important that no one else should be able to find the solution, $f(x)$, given only $g(x)$. Please help!

POSSIBLE EXAMPLE

This question/integral seems like it has some potential.

DEFINITION OF HARDNESS

The solution to the definite integral can be returned with the most $n$ significant digits correct. Then it is hard to do this if the time it takes is an exponential number of this time.

In other words, if we get the first $n$ digits correct, it would take roughly $O(e^n)$ seconds to do it.

Answer 1

I interpret your question as follows:

Is there any differentiable function $f$ and pair of real numbers $a,b$ such that computing the integral $\int_a^b f'(x)dx$ to $n$ bits of precision given $a,b,f'$ is substantially harder than computing $f(b)-f(a)$ to the same precision?

The answer to this is no, in the sense that if $f(b)-f(a)$ can be computed in $O(h(n))$ then the integral can be computed in $O(h(n))$ as well, assuming $\lim\limits_{n\to\infty} h(n)=\infty$. One way to do this would be to simply enumerate all functions with finite-length definitions and differentiate them until one is found with derivative $f'$. One might object that it is impossible to determine whether two strings of symbols produce the same function, but there are only countably many algorithms for symbolic differentiation. Any algorithm used to differentiate $f$ must be a provably correct implementation of differentiation, and one can enumerate these by enumerating the list of all algorithms and of all proofs using the standard pairing function and checking each pair (algorithm,proof) to see if the proof proves the correctness of the algorithm. We can thus enumerate all pairs (function, provably correct differentiation algorithm). Thus we get the function $f$. This is obviously done in constant time w.r.t. $n$, and so if we can compute $f(b)-f(a)$ in $O(h(n))$ we can compute the integral in $O(h(n))+O(1)=O(h(n))$.

Answer 2

This seems off what you are asking, but you should know it since it changes what you want. Volterra came up with an example of a function on, as I recall, the open interval $(0,1)$ which has a derivative at every point. The derivative is bounded but discontinuous on a Cantor set of positive measure. As a result, the derivative does not have an integral: possession of a definite Riemann integral is equivalent to the set of points of discontinuity being of measure zero. The example is in Counterexamples in Analysis by Gelbaum and Olmsted. I will see if I can find something on line. HERE

EDIT: the Volterra derivative does not have an indefinite integral either. This comes late in the Beamer talk by Bressoud referenced on WickedPedia.

Answer 3

Find two large primes $p$ and $q$, call their product $N$; then it's easy for you to compute $\int_{J(N)}1\,dx$, where $J(N)$ is the interval between the prime factors of $N$, but for anyone else to compute the integral, she would have to factor $N$ first.

Answer 4

Here is an example (by Harold Davenport) of a function that is hard to integrate:

$$\int{2t^6+4t^5+7t^4-3t^3-t^2-8t-8\over (2t^2-1)^2\sqrt{t^4+4t^3+2t^2+1}}\,dt\ .$$ The primitive is given by (check it!) $$\eqalign{&-2\log(t^2+4t+2)-\log(\sqrt2+2t)\cr&+ \log\left(\sqrt2 t+2\sqrt2-2\sqrt{t^4+4t^3+2t^2+1}\,\right)\cr &-5\log(2t^2-1)-5\log\left(2\sqrt2 t+4\sqrt2 -t^2-4t-6\right) \cr&+ 5\log\left(\bigl(4\sqrt2+19\bigr)\sqrt{t^4+4t^3+2t^2+1}\right. \cr &\qquad\qquad\left. - 16\sqrt2 t^2 -8\sqrt2 t +6\sqrt2 -29t^2-38t+5\right)\cr}$$ $$\eqalign{ &+ 2\log\left(\bigl(10\sqrt2+17\bigr)\sqrt{t^4+4t^3+2t^2+1}\right.\cr &\qquad\qquad\left.+4\sqrt2 t^2+16\sqrt2 t -2\sqrt2-11t^2-44t-39\right) \cr &+ {1\over2}\log\left(\bigl(731\sqrt2 t+71492\sqrt2-70030t-141522\bigr) \sqrt{t^4+4t^3+2t^2+1} \right.\cr &\qquad\qquad-40597\sqrt2t^3-174520\sqrt2t^2-122871\sqrt2 t+50648\sqrt2\cr&\qquad\qquad\left.+90874t^3+ 403722t^2+ 272622t-61070 \vphantom{\sqrt{t^4}}\right)\cr & + {(2t+1)\sqrt{t^4+4t^3+2t^2+1}\over 4t^2-2}\ .\cr}$$