3
$\begingroup$

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.

  • 4
    The ease or difficulty of integrating $g$ would likely depend on how skilled the one doing the integration is at seeing a pattern...2012-07-23
  • 3
    "Hard to integrate" is not a very precise standard. What is your motivation for asking this question?2012-07-23
  • 0
    @J.M.: Perhaps a group of integrals would be needed, in the hopes that at least one would evade pattern recognition. I wonder what integrals are generally considered hard to integrate, to start...2012-07-23
  • 3
    "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 integral2012-07-23
  • 0
    @Potato: I'm curious about one-way functions, as they're refered to in cryptography. I wonder if anyone has studied using integrals in this way. I think that they could be useful in the future, especially considering that electronic security seems to be increasingly important.2012-07-23
  • 0
    @ArturoMagidin: Thanks for your input. Perhaps it would be good to consider numerical methods as a standard. Where could I begin to find integrals that seem to take an exponential time to numerically evaluate?2012-07-23
  • 4
    @MattGroff: Numerical methods are for computing *definite* integrals. Your question seems to be about computing **indefinite** integrals. Which is it?2012-07-23
  • 0
    @MattGroff: I don't think there are *any* definite integrals that take "exponential time to evaluate", because any complicated function will necessarily require an approximate evaluation *anyway*, and there are a lot of very fast, very efficient, methods for estimating values of integrals (e.g., [Simpson's Rule](http://en.wikipedia.org/wiki/Simpsons_rule) is very good).2012-07-23
  • 0
    @MattGroff: Like I said, I'm not aware of any proposals in either direction; nor of any proposal of *trapdoor* functions involving integrals.2012-07-23
  • 0
    Does anyone see any potential integral that takes exponential or close to exponential time to evaluate?2012-07-23
  • 0
    Matt, "exponential" in what? What would be the size of the input here?2012-07-23
  • 0
    @J.D.:That's a good question! We could consider the range of the limits of integration, or the size of the desription of the integral. I believe the best bet, however, would probably be the level of precision. In other words, time to solve would be an exponential function of the correct significant digits returned in the solution.2012-07-23
  • 2
    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.2012-07-23
  • 1
    If you define *hardness* as in *one needs o cmpute a lot to aproximate the value with such and such precision*, you can look at functions which have very big oscillation.2012-07-23
  • 0
    If the encoded message is to consist of a numerical value of a definite integral, then you're vulnerable to at least two kinds of attacks: (1) the attacker succeeds in performing the indefinite integral, or (2) the attacker is able to analyze the expression well enough to do adaptive integration http://en.wikipedia.org/wiki/Adaptive_quadrature , which only requires figuring out where the function has bad behavior. Neither of these seems hard enough that I would trust them for crypto.2012-07-23

4 Answers 4

2

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

  • 0
    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.2012-07-23
  • 0
    @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.2012-07-23
  • 0
    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.2012-07-23
  • 0
    @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.2012-07-23
6

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.

3

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

  • 0
    Could you reveal the source of this integral? I'm not familiar with Daveport, but I'd like to know more...2012-07-23
  • 0
    @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.2012-07-23
  • 0
    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.2012-07-23
  • 0
    I posted a related question to this question and answer here: http://math.stackexchange.com/questions/176000/is-it-possible-to-get-an-easy-answer-for-int-frac-px-qx1-2-rx2012-07-28
2

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.

  • 1
    I seem to remember hearing something about factoring being done in polynomial time, but maybe that statement has such been retracted...2012-07-23
  • 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).2012-07-23
  • 0
    Well yes, but the hard part is finding the endpoints rather than doing the integration.2012-07-27