There’s an asymmetry between calculating the derivative of an expression, and calculating the integral of an expression. I think there are pretty straightforward algorithms to differentiate any expression, whereas if you need to integrate an expression there is no general approach that is guaranteed to work, and in fact no guarantee that it is even possible to write an expression for the integral. At least, that’s how I understand it. What’s the reason? Why, for example, couldn’t there have been some kinds of expressions whose derivatives have to be searched for with no guarantee of success?
I don’t mean the unknowable addend that is part of indefinite integrals, the constant of integration. I mean the difference in how one can approach figuring out the problem.
I don’t have a complete answer (I don’t know if a complete answer is ever even possible, for a “why” question), but it’s at least partly an artifact of the set of functions that we’ve chosen to call “standard functions”. Like, sine and cosine are considered “standard functions”. Which doesn’t actually present a problem here, since we know how to both differentiate and integrate those. But we could also contrive some other function for which we can’t express the derivative, and call that new function a “standard function”.
Interesting point, Chronos. But isn’t it really an artifact of how functions are arranged together to form expressions? I can’t think of any functions we don’t know both how to differentiate and integrate. Isn’t it when those functions get grouped and acted upon together that the difficulty arises? There are simple rules about how to differentiate them, but the “rules” for integrating are (I think) sometimes really just possible strategies.
""Here note this very remarkable fact, that we could not have integrated in the above case [𝑦=𝑎log𝑐𝑥+𝐶
y
a
log
c
x
+
C
] if we had not happened to know the corresponding differentiation. If no one had found out that differentiating log𝑐𝑥
log
c
x
gave 𝑥−1
x
−
1
, we [would] have been utterly stuck by the problem [of] how to integrate 𝑥−1𝑑𝑥
x
−
1
d
x
. Indeed it should be frankly admitted that this is one of the curious features of the integral calculus :- that you can’t integrate anything before the reverse process of differentiating something else has yielded that expression which you want to integrate."
Calculus Made Easy, p199.
Whoops! I’m wrong about how to define “function” when I say there aren’t any functions whose integrals are unknown. I’m thinking of things we write as irreducible phrases and ignoring the fact that any expression is a function. There are very simple expressions, functions, that have “non elementary integrals” listed here:
It should also be noted that, when it comes to the result existing, rather than being expressible, it’s the other way around: There are plenty of functions for which a derivative just plain doesn’t exist, but which can be integrated (given a suitable extension of the definition of integration). For the extreme example, the Dirlichet function (zero for irrational arguments, 1 for rational arguments) is nowhere differentiable, but integrates to 0.
For any notation, one can construct an algorithm which is guaranteed to eventually produce an integral, for any input function whose integral can be expressed in that notation. But that still doesn’t change the fact that not every function’s integral can be expressed in that notation. And in fact, I think the problem is sufficiently rich that it’s the case that you couldn’t always tell if a function falls into that category: That is to say, there will be some input functions for which the algorithm runs and runs and runs, and you can’t tell whether it’ll never end, or just takes a long time and hasn’t ended yet.
It’s also interesting that the answer is different depending on whether you’re talking about symbolic differentiation and integration, as we are, or numerical approximations. Numerical integration from discrete data is a much easier and stable problem than numerical differentiation.
A proper algorithm should either output an elementary anti-derivative, or prove there is none (it’s not too hard to come up with examples of the latter case for the usual school calculus notion of elementary function), not run forever
ETA there are some related problems known to be undecidable, so if your integration problem falls into that category there is no algorithm.
Should, yes. But what should be is not always what’s possible. I can’t prove it (as in, I personally can’t prove it, but I wouldn’t be surprised if someone else has), but I very strongly suspect that any program that’s guaranteed to halt will only do so by giving a result of “can’t be done” for some integrals that can in fact be done, if the integrator had just tried a little harder.
The first thing you have to do is define the problem clearly. If, for example, you stick to polynomials then they can all be integrated producing polynomials.
The way this question is generally considered is to start with a notion of elementary functions and ask whether the derivative of a function in that class lies in that class and whether there is an antt-derivative that lies in the class. For the purpose of elementary calculus, this is usually the closure under composition of polynomials, exponentials (which includes the standard trig functions is you use complex numbers), 1/x for x ><0, and roots. If you do that the class is closed under differentiation and is known not to be closed under anti-differentation. That is simply a fact, no different from any other fact and you cannot give a reason except by proving what I said above (and I have never seen a proof, only the claim).
On the other hand, suppose I define my elementary class as the set of all power series \sum_{i=0}^\infty a_i z^i that converge for |z| < 1. In that case it is relatively straightforward to show that the class is closed under both differentiation and and anti-differentiation.
The proof that it’s closed under differentiation would consist simply of the set of rules for constructing derivatives, and the observation that those cover all of the ways of assembling the elementary operations into functions.
For the proof that it’s not closed under integration, you’d only need one example, but I don’t know which example is easiest to prove, nor what the proof looks like. Maybe the integral of the Gaussian function? That is, I know that’s one of the un-integrable ones, but I don’t know how easy that proof is.
I think it might even be worse than that. The algorithm is easy: you devise a mapping between expressions and integers (Gödel is a help here), and then simply count up the integers until you find the expression whose derivative is the one you want.
As you noted, if that expression doesn’t exist, it’ll just run forever. Worse, though, you can’t even check your answers reliably: it is sometimes undecidable whether an expression A is equivalent to an expression B (or, equivalently, whether an expression is always equal to 0) (I’m guessing this is what @DPRK was referring to).
I hadn’t realized that about equivalence-checking. I think it’s at worst the same sort of indeterminacy, equivalent to the halting problem… except that if so, you still can’t combine them into a single halting problem, because the equivalence-checking would go the other way: If two expressions aren’t equivalent, you’ll eventually prove that, but if they are, your program might run forever.
Except, wait… If two expressions are equivalent, then isn’t there always some sequence of algebraic steps that will convert one to another? You could just systematically try all possible algebraic steps, and conclude when you find a sequence of steps that works. Meanwhile, I’m pretty sure that two functions expressible in the standard notation are equivalent iff they agree at every rational argument, so you could run in parallel an algorithm that systematically tries every possible rational argument in both expressions. By running those two algorithms in parallel, you’d be guaranteed to eventually return a result one way or the other (though it might take a very long time).
I confess I have not read Richardson’s book, but that’s right, for an example of a “problematic” situation, it follows from one of Richardson’s theorems that if you include the absolute-value function along with your exponentials, sines, and rational numbers then it becomes undecidable to figure out whether two expressions are equal or an expression is identical to zero, which will also put a stop to any algorithm (that does not run forever…) for symbolic integration in that case.
That’s like saying that if some statement or identity is true, then there is always some sequence of steps proving so: evidently not. Now the MDPR theorem says that for any recursively enumerable set of natural numbers there is a polynomial p(y, x1, … , xk) such that n is a member of that set if and only if there exist some integers such that p(n, x1, …, xk) = 0. So what Richardson did was start with a recursively enumerable set, hence a polynomial, for which it is undecidable whether there are solutions to p(n, x1, …, xk)=0.
This suggests an interesting question: given that there are categories of expression that are always both integrable and differentiable, do we know other categories that are one, the other, and neither? I’ll stipulate you can challenge that by saying I’ve just turned it into a debate about what constitutes a “category”…
I see no reason that this should be true. It is for polynomials and power series. There is a class of functions, called hypergeometric functions for which it has been shown to be true. It is a fascinating story since it was the doctoral thesis of a little known nun, Mary Celine Fasenmyer that disappeared without a trace until rediscovered by Herb Wilf. The details can be found in a book titled “A = B” by Wilf and Doron Zeilberger (it can be downloaded for free, incidentally). But this is just one case and I doubt that there will be general algorithms.
Please call them classes. Category is a special term with a specific meaning. What you seem to be asking is whether there are natural classes of functions with those specific properties. I already mentioned two classes that have both derivatives and integrals. The so-called elementary functions have derivatives but not every function in the class has an integral in the class. I think square roots of some rational functions (quotients of polynomials) are examples, but I am not certain. For classes that have integrals but not derivatives, it is easy enough to create one, but it seems silly. Polynomials of degree at least one would give such a class.
