# Why is differentiating mechanics and integration art?

It is often said that "Differentiation is mechanics, integration is art." We have more or less simple rules in one direction but not in the other (e.g. product rule/simple <-> integration by parts/u-substitution/often tricky).

There are all kinds of anecdotes alluding to this fact (see e.g. this nice one from Feynman). Another consequence of this is that differentiation is well automatable within CAS but integration is often not.

My question
We know that there is a deep symmetry based on the Fundamental theorem of calculus, yet there seems to be another fundamental structural asymmetry. What is going on here...and why?

Thank you

EDIT
Some peope asked for clarification, so I try to give it. The main objection to the question is that asymmetry between two inverse operations is more the rule than the exception in math so they are not very surprised by this behaviour.

There is no doubt about that - but, and that is a big but, there is always a good reason for that kind of behaviour! E.g. multiplying prime numbers is obviously easier than factoring the result since you have to test for the factors doing the latter. Here it is understandable how you define the original operation and its inverse.

With symbolic differentiation and integration the case doesn't seem to be that clear cut - this is why there are so many good discussions taking place in this thread (which by the way please me very much). It is this Why at the bottom of things I am trying to understand.

Thank you all again!

-
differentiation increases entropy, integration reduces it, so physics answers the asymmetry (just kidding). –  Suvrit May 29 '11 at 16:49
The fundamental theorem of calculus tells you that they're inverses. That's not necessarily a symmetry. There are plenty of examples of functions that are easy to compute whose inverses are hard to compute: en.wikipedia.org/wiki/One-way_function –  Qiaochu Yuan May 29 '11 at 17:00
I think it just amounts to the existence of the chain rule (including in its multivariable forms) for differentiation, which makes differentiation easy; if it wasn't for that, you'd call differentiation an art as well. I.e., we think of "nice" functions as those built up by compositions from some basic stock of primitive functions we understand well; the chain rule allows us to take our knowledge of the derivatives of the primitive functions and easily build up from this knowledge of the derivatives of all other "nice" functions, in this sense. Integration has no such chain rule, so it's hard –  Sridhar Ramesh May 29 '11 at 20:17
Although it's usually said that integration is harder than differentiation there are many senses in which the opposite true. As linear operators in functional analysis, integration is often much better behaved than differentiation. When doing exact real arithmetic, integration over an interval is computable but differentiation is not. (Eg. see homepages.inf.ed.ac.uk/als/Research/lazy.ps.gz) –  Dan Piponi May 29 '11 at 23:48
Ryan, why is division harder than multiplication? –  Deane Yang May 30 '11 at 4:47

One relevant thing here is that you are referring to differentiating and integrating within the class of so-called elementary functions, which are built recursively from polynomials and complex exponential and logarithmic functions and taking their closure under the arithmetic operations and composition. Here one can argue by recursion to show that the derivative of an elementary function is elementary, but the antiderivatives might not be elementary. This should surprise one no more than the fact than the square of a rational number is rational, but the square root of a rational number might be irrational. (The analogy isn't completely idle, as shown by differential Galois theory.)

In other words, the symmetry you refer to is really based on much wider classes of functions (e.g. continuous and continuously differentiable functions), far beyond the purview of the class of elementary functions.

But let's put that aside. The question might be: is there a mechanical procedure which will decide when an elementary function has an elementary antiderivative (and if it does, exhibit that antiderivative)? There is an almost-answer to this, the so-called Risch algorithm, which I believe is a basis for many symbolic integration packages. But see particularly the issues mentioned in the section "Decidability".

There is another interesting asymmetry: in first-order logic, derivatives are definable in the sense that given some expansion of the structure of real numbers, say for example the real numbers as an exponential field, the derivative of a definable function is again definable by a first-order formula. But in general there is no purely first-order construction of for example the Riemann integral (involving quantification over finer and finer meshes). I seem to recall that there are similar difficulties in getting a completely satisfactory notion of integration for recursively defined functions on the surreals, due in part to the incompleteness (i.e., the many holes) in the surreal number line.

-
Let me add that I highly recommend Manuel Bronstein's book "Symbolic Integration I" (2005) on this topic. It is the closest you will find to a detailed account of the issues around implementing the Risch algorithm. –  Andres Caicedo May 29 '11 at 18:56
A similar question was asked in mathSE in February and I gave pretty much the same answer. At least the first part. Yours is much more complete. –  lhf May 30 '11 at 1:10
In this CS MIT video lecture (at 3:56) this issue is briefly discussed in the terms of pattern matching. "If I'm trying to produce integrals […] more than one rule matches. […] I may get to explore different things. Also, the expressions become larger. […] There's no guarantee that [it] will terminate, because we will only terminate by accidental cancellation. So that's why integrals are complicated searches and hard to do." However, the things you write are way above my head, so I’m not sure whether this adds anything to the discussion. –  mcb Aug 21 '13 at 18:32
@mcb I'm not sure how to pitch a response since you say what I wrote is above your head. I did watch a few minutes of the video. A key word is 'recursion': one can define formal differentiation on expressions that represent elementary functions by recursion, focusing on the last operation (addition, multiplication, composition, etc.) used to build an expression out of subexpressions, and recursively defining the formal derivative of the expression in terms of the subexpressions and their derivatives. These procedures are easy and are routinely taught to all calculus students. The Risch (cont.) –  Todd Trimble Aug 29 '13 at 20:20
@ToddTrimble Thanks for the link. In the lecture the mechanical difficulty of integration is explained by the fact that the rules for differentiation produce expressions which cannot be uniquely matched with the inverse rules (for example whether a $+$ was produced by the linearity of differentiation or by the product rule). I’m not sure whether this is trivial or a fact that has not been considered here. –  mcb Aug 29 '13 at 22:34
show 1 more comment

I want to try a different way of answering the question of why differentiation is somehow the "primary" operation and anti-differentiation the inverting operation. I'll try to make it as elementary as possible.

First let me say what I don't count as an answer. (This is not supposed to be a new contribution to the discussion -- just making my starting point explicit.) It's not enough to point out that differentiation obeys the product and chain rules and explicit differentiability of 1/x (thereby giving the quotient rule as well) and that anti-differentiation doesn't. Somehow one wants an answer that explains why we should have expected this in advance. I was going to say something about differentiation tending to simplify functions, but then realized that that's not really true: it may be true for polynomials but there are lots of functions for which it's false.

The small suggestion I wanted to make was to discretize the question and think about summation versus taking difference functions. Here the situation is slightly confusing because expressions like $\sum_{n=1}^Nf(n)$ tend to come up more often than expressions like $f(n)-f(n-1)$. But let's forget that and think about what it is that we have to do if we want to work out $\sum_{n=1}^Nf(n)$ explicitly. Usually we need to guess a function g and prove that $g(n)-g(n-1)=f(n)$ for every $n$, from which it follows by induction that $g(N)=\sum_{n=1}^Nf(n)+g(0)$. This (the finding of the function $g$) is a discrete analogue of anti-differentiating.

Looked at this way, to work out the sum we have to solve the functional equation $g(n)-g(n-1)=f(n)$ (where we are given $f$ and are required to solve for $g$). By contrast, when we work out the difference function we are solving the similar looking, but much easier, functional equation $g(n)=f(n)-f(n-1)$. It's much easier because the unknown function is involved only once: indeed, in a sense there's nothing to solve at all, but experience shows that we can usually simplify the right-hand side. Of course, with the first equation we can't simplify the left-hand side in a similar way because we don't know what $g$ is.

It's a bit like the difference between solving the equation $x^2+x=10$ and solving the equation $x=10^2+10$ (that is, the difference between algebra and arithmetic). So here is a real sense, in a closely analogous situation, where one operation is direct and the other is indirect and involves solving for something.

-
Thank you, I really like these kinds of intuitions! My question though would be why is it the other way round numerically? WLOG solving $x^2+x=10$ for x is obviously also numerically harder than solving $x=10^2+10$. Here symbolic and numeric complexity coincides but in the case of differentiation/integration often not - why? –  vonjd May 31 '11 at 8:32
The reason, I think, is that the analogy between the two situations isn't all that good. When you solve numerically you are trying to find a number. That coincides with what you are looking for when you solve a quadratic equation, whereas when you are antidifferentiating you are looking for a function, and numerical methods just give you function values. –  gowers Jun 1 '11 at 21:15

Differentiation is inherently a (micro-)local operation. Integration is inherently a global one.

EDIT: the reason that locality helps with symbolic differentiation of elementary functions (and is not present to help with symbolic integration of the same functions) is that the basic arithmetic operations used to build elementary functions are simpler locally than they are globally. In particular, multiplication and division become linear in the infinitesimal variables,

$$(f + df) (g + dg) \approx fg + f dg + g df$$

$$\frac{f+df}{g+dg} \approx \frac{f}{g} + \frac{g df - f dg}{g^2},$$

leading of course to the product and quotient rules which are two of the primary reasons why symbolic differentiation is so computable.

Note that properties such as holomorphicity, mentioned in the comments, are not quite as local as differentiation, because in order to be holomorphic at a point, one must not only be complex differentiable at a point, but also complex differentiable on a neighbourhood around that point. (In the jargon of microlocal analysis, it is merely a local property rather than a microlocal one.)

Finally, the reason why the inverse of a local operation (differentiation) is global is because differentiation is not locally injective (constants have zero derivative). In order to eliminate this lack of injectivity, one needs to impose a global condition, such as a vanishing at one endpoint of the domain.

SECOND EDIT: Another way to see the relationship between locality and computational difficulty is to adopt a computational complexity perspective. A Newton quotient, being local, only requires O(1) operations to compute. On the other hand, a Riemann sum, being global, requires O(N) operations to compute, where N is the size of the partition. This helps explain why the former operation preserves the class of elementary (or bounded complexity) functions, while the latter does not.

(This is only if one works in the category of exact calculation. If one is instead interested in numerical calculation and is willing to tolerate small errors, then the situation becomes reversed: numerical integration, being more stable than numerical differentiation, usually has lower complexity thanks to tools such as quadrature. Here, one can turn the global nature of integration to one's advantage, by allowing one to largely ignore small-scale structure, assuming of course that the integrand enjoys some regularity.)

-
I'm afraid I have to vote this down. How does the local-ness of differentiation make it more mechanical than integration? It seems to me (especially after the latest edit) that the question is about symbolic calculus, but your answer is about theoretical analysis. Though it would be interesting, if you had this in mind, to know how the global nature of integration influences, say, its effect on elementary functions. –  Ryan Reich May 30 '11 at 15:05
Ryan --- he's saying that computing the derivative is simpler because it only depends on local information at a point. Integration depends on information about every point on a fixed interval, simultaneously. Thus differentiation is fundamentally simpler than integration, simply from the definitions. Doesn't it seem a lot easier to organize the cutting down of a forest one tree at a time than having to cut them all down simultaneously? –  Peter Luthy May 30 '11 at 16:03
@Peter: In complex analysis, it is easy to prove that a holomorphic function is infinitely differentiable using Cauchy's integral formula, but very difficult to do so just from the definition of a derivative. The integral formula uses a path that is necessarily bounded away from the point at which you want to differentiate. So is differentiation still easier than integration just because it's local? –  Ryan Reich May 30 '11 at 16:24
My guess is, Ryan finds this unsatisfactory because maybe the question is referring of the algorithmic nature of the problems of integration and differentiation (one being essentially trivial when starting from a formula, the other not so much) and it is not clear how Terry's answer relates to that. –  Mariano Suárez-Alvarez May 30 '11 at 16:37
I've expanded upon my original answer in response to the above comments. –  Terry Tao May 30 '11 at 20:22

I hesitate to answer again, but I agree with comments by Deane Yang and others that so far the discussions haven't quite gotten to the bottom of things. (Not that I promise to succeed in doing so now, but let's see what happens.)

In a nutshell, you could say that differentiation succeeds largely because

• The derivative is a functor.

That's a modern-day way of stating the chain rule. One way to make this precise is by defining the derivative as a functor from the category of pointed smooth manifolds to the category of vector spaces, taking $f: (M, x) \to (N, y)$ to the linear map $Df_x: T_x M \to T_y N$ between the tangent spaces. The chain rule for smooth maps is exactly the statement that $D$ is functorial.

Better yet, it's a product-preserving functor. This is nice because it allows you to get at derivatives of other algebraic operations; for example, the product of two functions $f, g: \mathbb{R} \to \mathbb{R}$ is a composite

$$\mathbb{R} \stackrel{\Delta}{\to} \mathbb{R} \times \mathbb{R} \stackrel{f \times g}{\to} \mathbb{R} \times \mathbb{R} \stackrel{\text{mult}}{\to} \mathbb{R}$$

and so to derive the product rule, you just have to know how to take the derivative of that last map $\text{mult}$, and the product-preserving functoriality can take care of the rest.

Notice by the way that this point of view meshes very well with how Terry Tao emphasized the local aspects of differentiation; presently, the locality was handled by working with pointed manifolds. One can take this a little further and claim "morally" that the derivative functor is represented by a very local object (i.e., an object with one point), sometimes called "the walking tangent vector". This would be something like

$$T = Spec(\mathbb{R}[x]/(x^2))$$

so that the tangent bundle of a manifold $M$ is the manifold of smooth maps $T \to M$. Suffice it to say that all this can be effectively formalized in synthetic differential geometry (SDG), where in fact the category of manifolds can be fully embedded in a suitable smooth topos $\mathcal{T}$, and the derivative functor becomes an internal hom-functor

$$(-)^T: \mathcal{T} \to \mathcal{T}$$

So in summary, the derivative functor is represented by a local object, and this representability can be regarded as "explaining" the product-preserving functoriality (insofar as representable functors preserve products).

All this is to suggest that the motto "integration is inverse to differentiation" might be adopting a very misleadingly narrow view of what differentiation is. In the present context, I think we were considering primarily the case of real-valued functions on an interval, but this masks the fact that the derivative is something far more general and functorial and representable on a larger category.

I am having a hard time understanding integration in anything like these terms, so I'm thinking this could be suggestive of what's going on here.

-
Now we need to involve $(1,\infty)$-groupoids somehow and we are set :) –  Mariano Suárez-Alvarez May 30 '11 at 22:30
No, no, no; its with $(0,∞)$-groupoids that we are $\mathrm{Set}$ –  Sridhar Ramesh May 30 '11 at 22:59
@Mariano: I'm not sure what to make of your comment. Is there anything unreasonable in my answer that you'd like to point out? (Same to whoever voted my answer down.) –  Todd Trimble May 30 '11 at 23:10
A related point is that differentiation can be defined in much more general settings than real-variable ones (e.g. formal differentiation of algebraic maps on varieties over an arbitrary field), whereas integration is mostly restricted to real-variable (and complex-variable) settings. So whereas integration needs both analysis and algebra, differentiation needs only algebra, which helps explain why it is simpler. –  Terry Tao May 31 '11 at 1:21
Something that puzzles me a bit, when seeing the differential of a function $f:\mathbb{R}\to\mathbb{R}$ as a map of vector bundles $df:T\mathbb{R}\to T\mathbb{R}$ on the real line manifold, is that it already contains all the information about its "antiderivative": indeed it's defined by $(x,v)\mapsto d_x f(v):=(f(x),f'(x)\cdot v)$. That is, if somebody gives you the derivative of a function as a map of vector bundles on the real line, then you are trivially able to reconstruct the function. –  Qfwfq Oct 2 '12 at 19:02

Todd Trimble's (fantastic) answer is the clear limiting factor as to why integration is harder in this setting. But I think this leaves the OP scratching his head: why do we take the point of view that differentiation is the basic operation and integration is the inverse? The answer is that there is a good reason it is harder but that people still take this point of view.

One could attempt to take the opposite point of view and assume integration is the "basic" operation and that differentiation is the opposite of integration; the basic question is then: given a function $g$, when do we have an $f$ such that $g(x)=C+\int_0^xf(t)dt$? The answer is: whenever $g$ is absolutely continuous. This property is quite a bit stronger than regular continuity and also quite a bit more difficult to check (unless $g$ were Lipschitz, say). Continuity allows you to check each point, but for absolute continuity one essentially has to look at all points in an interval simultaneously. Thus transferring theorems about integrals to theorems about derivatives is more delicate.

Even so, this is in many ways the "modern" view of the derivative in analysis, e.g. Sobolev spaces, weak solutions to differential equations, and so on. The derivative is such a poorly behaving operator that it is actually more convenient to take this approach.

-
+1: I think you hit the nail on its head: "why do we take the point of view that differentiation is the basic operation and integration is the inverse?" Thank you for that! Then you write: "but for absolute continuity one essentially has to look at all points in an interval simultaneously." Two observations: 1. doing e.g. u-substitution (or any other integration-'rule') you don't actually 'check' for some continuity conditions. 2. finding a derivative means also finding a function which is valid for all points simultaneously, too. So the reason for the asymmetry is still not clear to me. –  vonjd May 30 '11 at 6:10
1. u-sub is a statement about derivatives pushed into integration via the fundamental theorem of calculus: it's just a restatement of the chain rule. You can still prove a version of u-sub for absolutely continuous functions, but it takes more work. 2. You still need to check continuity at each point, but you can basically check the points one-by-one. But in any case, every absolutely continuous function is continuous, but plenty of continuous functions are not absolutely continuous. Indeed I would guess "most" continuous functions are not absolutely continuous. Isn't that an asymmetry? –  Peter Luthy May 30 '11 at 6:41

(I've split this off from my original answer, as it is unrelated to that answer.)

A counting (or entropy) argument can also be used to heuristically indicate why inverting differentiation should not be easy. One can empirically verify that if one differentiates an elementary function of complexity N (i.e. it takes N mathematical symbols in order to describe it), one usually obtains an elementary function of complexity greater than N. (Polynomials are an exception to this rule, but they are virtually the only such exception. Not coincidentally, polynomials are one of the rare subclasses of elementary functions for which integration is easy.) If differentiation was invertible within the class of elementary functions, this would suggest that if one integrated a typical elementary function of complexity at most N, one should get an elementary function of complexity strictly less than N. (This is unfortunately not a rigorous implication, because the notion of "typical" need not be preserved by differentiation or integration, but let us suspend this issue for the sake of the heuristic.) But there are significantly more functions in the former class than the latter (the number of functions of a given complexity grows exponentially in that complexity), a contradiction.

Note though that the above argument is quite far from rigorous. There are certainly many operations (e.g. inverting a large square matrix) such that both the operation and its inverse (which, in the case of matrix inversion, is itself) map bounded complexity objects to bounded complexity objects, and typically increase complexity. However, it does suggest that in the absence of any particular reason to believe that inversion is easy, the default assumption should be that inversion is hard.

-

"Inverse" does not always mean "symmetric". It is pretty mechanical to map $x\mapsto x^3+x^2-5$, and it was an art of 16th century to find an $x$ which maps, say, to $0$.

Or, less mathematical, it is easy to mix a glass of rice with a glass of oats, and it is pretty more a matter of art to get them back to proper glasses.

-
@harecare: I understand that but my question why this asymmetry is the case here. –  vonjd May 29 '11 at 19:52
@vonjd: what harecare is saying is that there's no special reason to expect a symmetry. That is, a function and its inverse should be "asymmetric until proven symmetric" rather than the other way around. –  Qiaochu Yuan May 29 '11 at 20:24
Exactly for the same reason as for polynomials above: differentiating is a map from functions to functions and integration is trying to revert it - to find a preimage. Nobody ever promised that the inverse action should be as easy as the original one. –  harecare May 29 '11 at 20:30
@harecare: I thought about your comment and don't fully understand it: integration is also a map from functions to functions, isn't it. And the definition of preimage seems a little arbitrary to me, but perhaps I am mistaken... –  vonjd May 30 '11 at 5:57
A map is a rule of preparing for each object from A one object from B. Let me illustrate. Suppose you prepare from each decimal number the sum of its digits: from 231 you get 6, and so on. This is absolutely routine. But now you ask, which numbers give you 6, the preimages of 6? Looks more challenging, isn't it? Finding preimages is not a map, because for one object you may get several. And what if you are asked to find minimal of those preimages? This weird task is in the spirit of integration problems of traditional calculus: you are asked to find a very special form of answer. –  harecare May 30 '11 at 7:09
show 1 more comment

Of course, I voted Todd Trimble's answer, but I want to address an other aspect of the question.

Somehow, integration is not the inverse of differentiation. If $f:(a,b)\mapsto\mathbb R$ is differentiable, its derivative at each point $x$ is well-understandable, but $f'$ might be ugly as a function. A. Denjoy characterized (or tried to characterize ?) the functions $g:(a,b)\rightarrow\mathbb R$ that are derivatives of everywhere differentiable functions $f$. He used transfinite induction to resconstruct $f$ from $f'$. Of course, integration provides the answer when $g$ is continuous, or integrable, but not in general.

Example. If $\alpha\ge1$, the function $x\mapsto x\sin\frac1{x^\alpha}$ is differentiable everywhere, yet its derivative is not integrable. I am sure that there are much worse examples, where $f'$ is not integrable on any non-trivial interval. The only necessary conditions I see about the derivative $f'$ of an everywhere differentiable function are

• $f'$ is measurable, because it is the pointwise limit of a sequence of continuous functions (the quotients),
• $f'$ satisfies the intermediate value property: if $c\in(f'(x),f'(y))$ then there exists a $z$ between $x$ and $y$ such that $f'(z)=c$. This follows from Rolle's Theorem.
-
@Denis: Thank you for your answer. Can you perhaps give an example of "Somehow, integration is not the inverse of differentiation." –  vonjd May 30 '11 at 9:52
@vonjd: most functions are not integrable. When $g$ is continuous, the fundamental theorem of calculus tells you that $g$ is the derivative of $\int_a^x g(t)dt$. But if $g$ is not integrable, this obviously cannot hold, yet it may be that $g$ is a derivative nonetheless. I don't have a specific example in mind right now. –  Thierry Zell May 30 '11 at 10:02
OK, now I see what you mean - I guess there are also many examples the other way around (i.e. integrable but not differentiable, e.g. Dirichlet function, Wiener process etc.) - still, even in the cases where everything is nice and well behaved the asymmetry holds: differentiating is mechanics and integration is art... –  vonjd May 30 '11 at 10:38
@Denis: Thanks for fleshing out your answer. I wish I could vote this answer up a second time! –  Thierry Zell May 30 '11 at 15:11
follow up here mathoverflow.net/questions/66462/… –  Pietro Majer May 31 '11 at 7:16

Todd Trimble's answer that the derivative in the disguise of the tangent mapping is a functor is the perfect answer. But I want to elaborate a little also on his first answer:

• What are elementary functions?

An answer that I often gave in introductory courses is: Solutions of linear ODEs with specal constant (integer?) coefficients of low order.

If we would give names to solutions of corresponding integral equations, maybe then formal integration would look easier, as it is numerically.

From elementary functions (maybe better, functions with names) we construct other functions by composition, etc. These we want to integrate.

For formal integration we could consider expressions like $df = f'dx$ with the usual rules; in particular $d(f\circ g) = (f'\circ g) g' dx$ and integration by parts $d(fg) = f.dg + g.df$ Call anything of the form $df$ a total differential. Then the game is: Reduce it to a sum of total differentials. Then remove all $d$'s, and you integrated the given 1-form $fdx$. Let me paraphrase this as: Formal integration is a cohomological operation (or anti-operation).

-
Can you expand on this? You seem to be saying that with respect to the right "basis" integration could be made routine, behaving in a similar way to how differentiation behaves on elementary functions. Is the difficulty that you'd also need to replace basic operations such as composition with some less natural/common counterparts? –  Noah Stein Oct 2 '12 at 17:32
I think this is the only answer that really touches on the ways of seeing why integration is harder than differentiation. This question cannot be answered by showing how easy is differentiation and how hard or even hard to define integration is. Specially if the functions to be treated are written already in ways that are easy for the derivative to treat. In a sense, we are giving (assuming) the input of the derivative already in a way that it is easy to compute. –  ABC Oct 31 '13 at 0:49

I might as well give my very, very vague philosophical take on the discussion so far (which, despite my obvious initial skepticism, has been extremely interesting).

First, from almost any perspective except for symbolic computations, I consider integration to be much easier to work with than differentiation.

As for formal symbolic computations, it appears to me that the point is that on the appropriate space of "functions that can be defined using a formula", the derivative is a linear operator that behaves nicely with respect to other natural operations, notably composition, multiplication, and division. On the other hand, the antiderivative operator (say, with some fixed initial condition) is a linear operator that does not have the same nice formal algebraic properties.

But of course this begs the question of why is this so. Trimble, Tao, and Gowers have posted very beautiful interesting answers, but I'm still not sure I get it. One important point, I think, is that differentiation arises via linearization, which is somehow a simplification (since at heart you're replacing a nonlinear function by a linear one). On the other hand, even though integration is also a linear operation, it arises through "antilinearization", which is somehow an "anti-simplification" (since at heart you're reconstructing a nonlinear function from all of its linear approximations).

-
I'm not sure I buy your argument that the linearization "is somehow a simplification". True, linear functions are simple, but the linearization we perform when differentiating varies from point to point in a nonlinear way, and it's the entire derivative we're interested in here rather than just the derivative at a point. (This is particularly clear if we look at functions of more than one variable, when the derivative is a decidedly more complicated object than the original function.) –  gowers May 31 '11 at 15:59
I have only circular arguments on why linearization is simpler than the reverse, namely what I say in the penultimate paragraph. Somehow linearization is formally (algebraically) a nice operator, whereas reconstructing a nonlinear function from its linearization is not. But otherwise I can understand your skepticism. –  Deane Yang May 31 '11 at 16:13
@Deane: Now I am totally confused - on the one hand Tao says that differentiation is inherently local - and therefore easier. On the other hand I thought (and said it above) that differentiation is also global (in a way) because you are trying to find a function which satisfies the whole domain (and not only one point). Now Gowers seems to support this point. Isn't this a contradiction? The whole matter gets more and more mysterious (at least to me)... –  vonjd May 31 '11 at 17:01
vonjd, any local operation can be made global (by just doing it everywhere). I'll add a few more vague comments to my answer when I get some time. –  Deane Yang May 31 '11 at 18:30
@Deane: I would very much appreciate that - thank you! –  vonjd Jun 9 '11 at 6:46

Both derivatives and integrals are limits. Now consider what they are limits of. Clearly, a difference quotient is a simpler expression than a sum of a bazillion terms.

-

The reason is entirely that the product rule for differentiation allows you to compute the derivative of a product by induction on the factors. Many of the "hard" integrals you probably have in mind are constructed from polynomials, exponentials, and logarithms by composition and the algebraic operations (meaning that they are "elementary" in the sense that Todd Trimble discusses), so by using the chain rule, in the form of u-substitution, you can reduce their computation to integrating lots of products whose terms are individually easy integrals. If something like the product rule existed, this would be doable, but the fact that $$\int e^{-x^2} dx = \int e^{-u} \frac{1}{2\sqrt{u}} du$$ is not elementary means that there is no hope of such a convenient method.

-

[Edit: belatedly, I realize that Todd has already mentioned the Risch algorithm in his own answer. Cutting this own down to the appropriate essentials.]

I do take exception to your statement that integration is not automated or implemented in CAS software. The Risch Algorithm is a lot more complicated than derivation (which used to be a routine project to assign to computer science students); I don't know that any CAS fully implements the algorithm, though all of them implement it at least partially; and this is about as good as it gets since there are elementary functions that do not admit elementary primitives.

On another note, I've heard integration referred to as an inverse problem by analysts; unfortunately, I couldn't find a good reference. But the idea was that direct problems and inverse problems are fundamentally different animals with different features. Direct problems (derivation, checking that a function satisfies an DE, multiplication of integers) have unique solutions that have simple algorithms. Inverse problems (integration, solving ODEs, factorization of integers) usually arise when you take a direct problem backwards, and this almost dooms them to being more complicated. Usually, even proving that a solution exists is an achievement, the solutions may be harder to get to, and usually are not unique.

-
But why is differentiation the "direct" problem and integration the "inverse" problem, and not the other way around? –  Michael Lugo May 30 '11 at 2:27
@Michael Lugo: Perhaps it depends how you define the problem. Formal calculus on polynomials is certainly equally easy for either operation. Likewise finite Fourier series. In both cases, we can apply linearity and consult a finite table of derivatives or antiderivatives. However, composition usually produces too many functions to admit only a finite table as sufficient, so this method doesn't go very far unless you want to use infinite series, where everything becomes truly mechanical except for figuring out which closed-form function you have. –  Ryan Reich May 30 '11 at 3:11
@Michael: You have a fair point. As I mentioned, this whole business of direct/inverse is stuff I heard in talks and conversations, but when I tried t pin down a specific reference while composing my answer, I found that it was like looking for a needle in a haystack because the terminology is used more loosely in scientific contexts (basically, to denote modeling, as far as I can tell). I'm pretty sure that you can make a good argument why integration is inverse, but right now the only thing I can think of is the non-uniqueness. –  Thierry Zell May 30 '11 at 3:50
Ryan --- I think all of my calculus students would disagree that Riemann sums are "easy" for polynomials. Indeed, I would have to agree with them! The computation only really becomes simple when you apply the fundamental theorem of calculus. –  Peter Luthy May 30 '11 at 4:42
@Michael: I think this question 'why this way around' hits the nail on its head! –  vonjd May 30 '11 at 6:12
This is a collection of a few ideas. Let me see where it takes us.
It is probably too verbose since I am writing it as I think the question.
Maybe later I can shorten it and correct errors.
If you are hurried it is safe to scroll down to the last part, where there is
what I think is an answer to the OP's question.


I want to concentrate on differentiation and integration as symbolic operations.

For differentiation we can consider a class $E$ of functions-symbols that contains the constants (complex constants maybe), $x$, is closed under the arithmetic operations, and composition. We can throw in other function-symbols like $e^x$, $\ln(x)$ together with $x^{-1}$, or many others. But notice that for every new function-symbol we throw in $E$ we assume we know how to compute its derivative (we have a symbol for it). The minimal assumption of having the constants and $x$ gives us $E$ to be the polynomials. A larger option would be the elementary functions.

If differentiation is considered as an operation in the symbols in $E$ then it is, by the definition of $E$, an algorithmic operation. Given a function-symbol from $E$ (which by this act it is assumed to be formed from a few symbols for which we know the derivative and arithmetic and composition operations) we can compute its derivatives because the properties of differentiation cover the operations generating $E$. In principle, what might be hard is the question of whether a function belongs to $E$.

Claim: Integration is, at least, as hard as derivation. (maybe harder)

This is clear for the case of polynomials, which are always contained
in a reasonable minimal E.


Observation: The tentative claim that integration is harder than derivation is going to necessarily depend on $E$, since for $E$ being the polynomials both are simple operations.

_


Let us consider now constructing a domain, as we have have done for differentiation, that is adapted to the operation of integration. Consider $I$ to be a collection of function-symbols, that contains the constants, $x$, and possibly others $e^x$, $x^{-1}$, ... for which we assume we know their integrals. Assume that $I$ is closed by the following operations:

If $f$ and $g$ are in $I$,

1. $af+bg\in I$ for any constants $a$ and $b$. And the operations:
2. $f\oplus g:=fg'+f'g\in I$
3. $f\otimes g:= (f\circ g)\cdot g'\in I$

An $I$ like this is a reasonable minimum domain in which to define integration. It is clear that in such an $I$, integration is algorithmic, for a given function written using these operations.

Claim: In $I$, derivation is simple if we assume $I$ contains the constants and either 2 or 3 are satisfied.

In fact, for a given f in I, its derivative is f'=f⊕1=1⊗f$.  This means that just one basic operation in$I$allows to compute derivatives. _  To translate the OP's question into another question: Given an$E$we already have a way to define linear combinations with constants,$\oplus$and$\otimes$, since these are defined using the operations allowed in$E$. So, for an$E$to be an$I$or to form out of it a$\subset I$we would need to have an algorithm that checks whether an element of$E$is an$I$(can be written using function-symbols with function-symbols integrals, linear combinations with constants coefficients,$\oplus$, and$\otimes$). We have that the existence of such an algorithm depends on the$E$, on the function-symbols available in it. For$E$being the polynomials in$x$it is clear we have such an algorithm and it is simple. We have also that for some$E$the problem is undecidable. From Richardson's theorem we know that if$E$: 1. Contains$\ln(2),\pi,e^x,\sin(x)$2. Contains$|x|$and 3. Contains a function with no primitive in$E$Condition$3$is satisfied for the$E$-closure of the elementary functions together with$|x|$, since we can take$e^{x^2}$to verify$3$. The theorem is true because they manage to prove there is an elementary function (using also$|x|$)$M(n,x)$which is identically to either$0$or$1$for each natural number$n$but for which it is undecidable for every natural number$n$whether it is identically$0$or$1$. Given such a function then, if we could decide integration in$E$, then we could decide, for each natural number$n$, whether$f_n(x):=e^{x^2}M(n,x)$is integrable or not. But this would tell us when$M(n,x)$is zero or one, since$f_n(x)$is integrable when$M(n,x)=0$and non-integrable in$E$when$M(n,x)=1$. So, for certain classes$E$we have that, while derivation is elementary (after having shown the function belongs to$E$), integration is undecidable. This already shows that integration is harder than derivation (the statement depending of course on the class of functions we want to integrate). Observation: The undecidability of integration for the$E$above is of course deeply related to having function-symbols in$E$without primitive function-symbol in$E$. This trivially disappears if we close$E$by throwing in it symbols for each primitive. On the other hand, the inconvenience is that this makes$E$not being generated by finitely many symbols. This makes the problem of detecting when a function is represented by a symbol in$E$even more complex. So, the reason why for this large$E$, if we are given a function which we know is in$E$we can compute its integral, is because we are pretty much assuming that we can by assuming that the input is in$E$. It remains then the question: Question: How small can$E\$ be such that integration is harder than derivation?

-

Why is integration harder for people than differentiation? This is as much a question about people and perception than it is about mathematics. Methods are ad hoc for the integrations that inspired the question, while software, for example Mathematica, uses rules to integrate that are just as mechanical as its rules for differentiation, as Stephen Wolfram explains in his book A New Kind of Science.

But performing the integration is only half the issue. The other half is making the answer look right, and for that the computer has to perform algebraic simplifications. This need for algebra is somehow intrinsic to these problems, e.g., even to verify an answer that looks different. So in a sense its difficulties are not different from the calculus student who needs to do algebra.

Why then is algebra hard, in particular algebraic simplification? Without getting too theoretical, just consider a typical adhoc procedure to integrate x^2*Exp[x]. We know that taking the derivative of x^n*Exp[x] gives two terms, and we can use that knowledge to predict the answer will be a combination of x^2*Exp[x], x*Exp[x], and Exp[x]. The behavior there allows us to solve for an answer.

Let's abstract from this example, where the terms are just linearly independent. The presence of terms is a binary condition, and one can think of taking the derivative as an operation like a cellular automaton. So an abstract model of the derivative operator is a cellular automaton.

Now that one has a model it is possible to investigate questions like the original question. Some cellular automata are reducible, in the same way that integrating x^n*Exp[x] is reducible, while others are irreducible and undecidable questions (i.e. there is no decision procedure) about them are common. So in the end it is basically the NKS phenomenon that Wolfram discovered.

-
@Todd: When you say: "harder for people" you mean that it is the same complexity both ways for a computer? The only thing that differs is the representation custom made for people which differs in its complexity? I think that only shifts the problem: Why is it that for symbolic differentiation representation is easy and for integration not? –  vonjd Jun 9 '11 at 6:51
VonJD: It is conceivable that another computational system would find integration easier. The second half of my post meant to address the human question. The CA analogy, where differentiation is like a step in a CA, shifts the problem to something easier to visualize. That reversing a CA is harder than computing its evolution is something one can see in the wild evolution of rule 30. One of the adhoc methods of integration is knowing what terms to include, and doing this is similar to reversing a CA, both in the cases where it is easy and where it is hard. –  Todd Rowland Jun 10 '11 at 17:10

I thought about this issue some time ago and I reached an interesting point of view I think. I believe it is worth to share it here. Of course it may be naive. Please feel free to comment.

Integration (antiderivation if you like) is not a "mapping" between a function and another function of the same dimensionality. After each integration a new "constant" appears. This new constant is a new degree of freedom or dimension.

From the recursive point of view this is very important I believe. Sometimes when you integrate (e.g. polynomials and exponentials/sin/cos) the new constant falls into the same family of functions that contained the original functions. For example, a constant is just a polynomial of degree zero or an exponential with zero "growing rate/frequency" (ie exp(0.x) = const. and cos(0.x)=1).

Notice also that the family of polynomials and exponentials are preserved by summation and multiplication. Polynomials also by function composition. So even a priory complicated expressions are just "solved" using the same procedure by recursion.

Now, when because of the new constant you fall outside of this family, for instance: exp(exp(x) + cte) is not in the same family as exp(x), then you need to grow your family and so your recursive method is more complicated. It may happen (in principle) that the (extended) family is infinite and so you cannot find a method at all! You just need a bible :).

In my view the new constants allow us to put more and more information about the real world into the expression (initial conditions, boundary conditions, some physical parameters, etc). Some times this constants are meaningless or do not have physical consequences. Other times they are physically important because your physical system increased in complexity due to this new constant. The new constant expanded the family of functions! More over, from a statistical point of view, sometimes a large number of integration constants are just equivalent to noise. In this case the microscopic description may be impractical but a macroscopic statistical description may be obtained. Furthermore, the aggregate contribution of the constants to some "macroscopic/statistical" quantities is incoherent and so the particular values of the constants are washed out.

In other cases, where complex systems as living systems reside, the integration constants are very important and cannot be ignored or "statistically reduced" to a small number. Using the words of Philip W Anderson more is different in this sense. These new integration constants sum up coherently and complexity arises.

Best Regards, Juan I. Perotti

-