Why is differentiating mechanics and integration art? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T20:23:20Z http://mathoverflow.net/feeds/question/66377 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art Why is differentiating mechanics and integration art? vonjd 2011-05-29T16:44:52Z 2012-10-02T18:59:54Z <p>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 &lt;-> integration by parts/u-substitution/often tricky).</p> <p>There are all kinds of anecdotes alluding to this fact (see e.g. this <a href="http://en.wikipedia.org/wiki/Differentiation_under_the_integral_sign#Popular_culture" rel="nofollow">nice one from Feynman</a>). Another consequence of this is that differentiation is well automatable within CAS but integration is often not.</p> <p><strong>My question</strong><br> We know that there is a deep symmetry based on the <a href="http://en.wikipedia.org/wiki/Fundamental_theorem_of_calculus" rel="nofollow">Fundamental theorem of calculus</a>, yet there seems to be another fundamental structural asymmetry. What is going on here...and why?</p> <p>Thank you</p> <p><strong>EDIT</strong><br> 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.</p> <p>There is no doubt about that - but, and that is a big <em>but</em>, there is always a good <em>reason</em> 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.</p> <p>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 <em>Why</em> at the bottom of things I am trying to understand.</p> <p>Thank you all again!</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66381#66381 Answer by Todd Trimble for Why is differentiating mechanics and integration art? Todd Trimble 2011-05-29T17:30:16Z 2011-05-29T17:30:16Z <p>One relevant thing here is that you are referring to differentiating and integrating within the class of so-called <a href="http://en.wikipedia.org/wiki/Elementary_function" rel="nofollow">elementary functions</a>, 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 <a href="http://en.wikipedia.org/wiki/Differential_Galois_theory" rel="nofollow">differential Galois theory</a>.) </p> <p>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. </p> <p>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 <a href="http://en.wikipedia.org/wiki/Risch_algorithm" rel="nofollow">Risch algorithm</a>, which I believe is a basis for many symbolic integration packages. But see particularly the issues mentioned in the section "Decidability". </p> <p>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. </p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66391#66391 Answer by harecare for Why is differentiating mechanics and integration art? harecare 2011-05-29T19:43:43Z 2011-05-29T19:43:43Z <p>"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$.</p> <p>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.</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66393#66393 Answer by Michael Renardy for Why is differentiating mechanics and integration art? Michael Renardy 2011-05-29T20:39:42Z 2011-05-29T20:39:42Z <p>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.</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66395#66395 Answer by Ryan Reich for Why is differentiating mechanics and integration art? Ryan Reich 2011-05-29T20:58:04Z 2011-05-29T20:58:04Z <p>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.</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66411#66411 Answer by Thierry Zell for Why is differentiating mechanics and integration art? Thierry Zell 2011-05-30T02:02:21Z 2011-05-30T02:09:30Z <p><strong>[Edit: belatedly, I realize that Todd has already mentioned the Risch algorithm in his own answer. Cutting this own down to the appropriate essentials.]</strong></p> <p>I do take exception to your statement that integration is not automated or implemented in CAS software. The <a href="http://en.wikipedia.org/wiki/Risch_algorithm" rel="nofollow">Risch Algorithm</a> 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.</p> <p>On another note, I've heard integration referred to as an <strong>inverse problem</strong> 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. </p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66419#66419 Answer by Peter Luthy for Why is differentiating mechanics and integration art? Peter Luthy 2011-05-30T05:36:49Z 2011-05-30T05:36:49Z <p>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: <b>why do we take the point of view that differentiation is the basic operation and integration is the inverse?</b> The answer is that there is a good reason it is harder but that people still take this point of view.</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66433#66433 Answer by Denis Serre for Why is differentiating mechanics and integration art? Denis Serre 2011-05-30T09:40:49Z 2011-05-30T15:01:40Z <p>Of course, I voted Todd Trimble's answer, but I want to address an other aspect of the question. </p> <p>Somehow, integration is <em>not</em> 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.</p> <p><strong>Example</strong>. 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</p> <ul> <li>$f'$ is measurable, because it is the pointwise limit of a sequence of continuous functions (the quotients),</li> <li>$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.</li> </ul> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66458#66458 Answer by Terry Tao for Why is differentiating mechanics and integration art? Terry Tao 2011-05-30T14:48:55Z 2011-05-31T01:13:50Z <p>Differentiation is inherently a (micro-)local operation. Integration is inherently a global one.</p> <p>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,</p> <p>$$(f + df) (g + dg) \approx fg + f dg + g df$$</p> <p>$$\frac{f+df}{g+dg} \approx \frac{f}{g} + \frac{g df - f dg}{g^2},$$</p> <p>leading of course to the product and quotient rules which are two of the primary reasons why symbolic differentiation is so computable. </p> <p>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 <a href="http://en.wikipedia.org/wiki/Microlocal_analysis" rel="nofollow">microlocal analysis</a>, it is merely a local property rather than a microlocal one.)</p> <p>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.</p> <p>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. </p> <p>(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.)</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66490#66490 Answer by Todd Trimble for Why is differentiating mechanics and integration art? Todd Trimble 2011-05-30T20:20:33Z 2011-05-30T20:20:33Z <p>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.) </p> <p>In a nutshell, you could say that differentiation succeeds largely because </p> <ul> <li><b>The derivative is a functor.</b> </li> </ul> <p>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. </p> <p>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 </p> <p>$$\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}$$ </p> <p>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. </p> <p>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 <i>pointed</i> 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 </p> <p>$$T = Spec(\mathbb{R}[x]/(x^2))$$ </p> <p>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 <a href="http://ncatlab.org/nlab/show/synthetic+differential+geometry" rel="nofollow">synthetic differential geometry</a> (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 </p> <p>$$(-)^T: \mathcal{T} \to \mathcal{T}$$</p> <p>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). </p> <p>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. </p> <p>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. </p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66497#66497 Answer by gowers for Why is differentiating mechanics and integration art? gowers 2011-05-30T22:14:40Z 2011-05-30T22:14:40Z <p>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.</p> <p>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 <em>in advance.</em> 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.</p> <p>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.</p> <p>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. </p> <p>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.</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66498#66498 Answer by Deane Yang for Why is differentiating mechanics and integration art? Deane Yang 2011-05-30T23:30:27Z 2011-05-30T23:30:27Z <p>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).</p> <p>First, from almost any perspective except for symbolic computations, I consider integration to be much easier to work with than differentiation.</p> <p>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.</p> <p>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).</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/66510#66510 Answer by Terry Tao for Why is differentiating mechanics and integration art? Terry Tao 2011-05-31T01:16:45Z 2011-05-31T01:16:45Z <p>(I've split this off from my original answer, as it is unrelated to that answer.)</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/67170#67170 Answer by Todd Rowland for Why is differentiating mechanics and integration art? Todd Rowland 2011-06-07T18:09:03Z 2011-06-07T18:09:03Z <p>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 <a href="http://www.wolframscience.com/nksonline/page-1177c-text" rel="nofollow">Stephen Wolfram explains</a> in his book A New Kind of Science.</p> <p>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.</p> <p>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.</p> <p>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 <a href="http://www.wolframscience.com/nksonline/page-53" rel="nofollow">cellular automaton</a>. So an abstract model of the derivative operator is a cellular automaton. </p> <p>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. </p> http://mathoverflow.net/questions/66377/why-is-differentiating-mechanics-and-integration-art/108633#108633 Answer by Peter Michor for Why is differentiating mechanics and integration art? Peter Michor 2012-10-02T13:26:27Z 2012-10-02T18:59:54Z <p>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:</p> <ul> <li>What are elementary functions?</li> </ul> <p>An answer that I often gave in introductory courses is: Solutions of linear ODEs with specal constant (integer?) coefficients of low order.</p> <p>If we would give names to solutions of corresponding integral equations, maybe then formal integration would look easier, as it is numerically. </p> <p>Answer to the comment:</p> <p>From elementary functions (maybe better, functions with names) we construct other functions by composition, etc. These we want to integrate.</p> <p>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).</p>