Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
The ease or difficulty of integrating $g$ would likely depend on how skilled the one doing the integration is at seeing a pattern... –  J. M. Jul 23 '12 at 0:13
2  
"Hard to integrate" is not a very precise standard. What is your motivation for asking this question? –  Potato Jul 23 '12 at 0:17
2  
"No one should be able to find the solution" is not very precise either. With "one way functions", we usually talk about the complexity of finding the input given the output, and expect it to be "of high complexity" (e.g., exponential on the input). The complexity will depend on the algorithm used to attempt to integrate a given function. Of more use are trapdoor functions, in which an extra piece of information, $h$, makes is so that there is an easy algorithm for computing $f$ given $g$ and $h$, and no known easy alg. for computing $f$ given $g$ alone. I don't know any such with integral –  Arturo Magidin Jul 23 '12 at 0:21
3  
@MattGroff: Numerical methods are for computing definite integrals. Your question seems to be about computing indefinite integrals. Which is it? –  Arturo Magidin Jul 23 '12 at 0:31
1  
I know double-posting is frowned upon, but you might want to post at cstheory.SE, since some crypto & complexity theory folks reside over there. –  user2468 Jul 23 '12 at 1:16

4 Answers 4

up vote 2 down vote accepted

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))$.

share|improve this answer
    
There is a trivial way to produce an infinite number of algorithms for symbolic differentiation: you tack on silly expressions like $\mathord{} + K - K$ to the answer. –  Zhen Lin Jul 23 '12 at 6:44
    
@ZhenLin Yes, but I mean finitely many he might be using. Anyway, countably many makes no difference, since whichever algorithm is actually being used will be tried after some finite number of tries. –  Alex Becker Jul 23 '12 at 8:51
    
I'm not convinced. One must have a computable enumeration of all algorithms that compute derivatives, and by Rice's theorem there is no such enumeration. –  Zhen Lin Jul 23 '12 at 8:54
    
@ZhenLin True, but any algorithm that he could use would have to be provably correct, and there is a computable enumeration of all algorithms that can be proven to correctly implement differentiation. –  Alex Becker Jul 23 '12 at 8:58

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.

share|improve this answer

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}$$

share|improve this answer
    
Could you reveal the source of this integral? I'm not familiar with Daveport, but I'd like to know more... –  Matt Groff Jul 23 '12 at 12:54
    
@Matt Groff: When Harold Davenport gave a talk at ETH Zurich one day in the eighties he had this example on one of his slides. He gave me a copy afterwards, and I used it many times to terrify my calculus students. He told me that he had more terrific examples in stock. –  Christian Blatter Jul 23 '12 at 18:11
    
Thanks for the information. I ran this through my math software, and it actually returned a pseudo-answer within a minute. The problem is, it returned the answer in a formula that needed the roots of the polynomials to be known and plugged in. So it makes me believe we could in fact create a generalized formula using a math program, and then create polynomials to plug into the equation. We would start with the roots, I guess, and then expand into polynomials. This would seem to indicate that solving these integrals is no harder than factoring polynomials. –  Matt Groff Jul 23 '12 at 19:09
    
I posted a related question to this question and answer here: math.stackexchange.com/questions/176000/… –  Matt Groff Jul 28 '12 at 3:45

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.

share|improve this answer
1  
I seem to remember hearing something about factoring being done in polynomial time, but maybe that statement has such been retracted... –  Matt Groff Jul 23 '12 at 17:09
1  
Primality testing can be done in polynomial time (in the number of digits), but if factoring can also, that's news to me (and would be major result). –  user7530 Jul 23 '12 at 19:41
    
Well yes, but the hard part is finding the endpoints rather than doing the integration. –  Robert Israel Jul 27 '12 at 21:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.