What is it fundamentally about symbolic integration that makes it so much more difficult to do? I mean, I studied calculus and learned any number of the rules but it's a curious thing that one operation, differentiation is trivial, yet the opposite, integration is massively complex.
This is a common feature of mathematics; doing many things is much easier in one direction than the reverse. Encryption systems are built on this idea, e.g. RSA relies on multiplication of large integers being very easy and factoring large integers being very hard. That doesn't really answer your question - I'm not sure there is a clear reason.
There is no general algorithm to symbolically compute all integrals. All we have are partial algorithms which consist of big rulebooks for the cases we’ve already solved.
It also turns out we can’t even verify, in general, the result of integration:
Suppose you are given two functions, f(x) and G(x), and are told that G(x) is an antiderivative of f(x). So then you let g(x) = G’(x), the derivative of G(x).
Now if G(x) is truly an antiderivative of f(x) then we must have g(x) = f(x) but unfortunately the problem of determining whether two functions are equal is undecidable (a consequence of the halting problem).
Does the functional equality being impossible to determine thing work for math problems? I know it works for computable functions, but math functions are pure and total so it seems easier.
Math functions are not total, in general. Computable functions are a subclass of all functions, so lots of functions are not computable.
Purity doesn't apply to functions, it applies to algorithms which compute functions. In software parlance the terms are often conflated but they are not equivalent. The algorithm which computes a function is in general not unique.
If you think of the variable being derived/integrated over as time, then conceptually the derivative at a time only represents information from that one time plus or minus some tiny delta, while an antiderivative repesents information from all of time.
Formally, I'm not sure how to show that's related to the relative difficilties of the two operarions, or if it actually is related in the first place, but intuitively the explanation is appealing.
So it's important to keep in mind the difference between integral and anti-derivative.
And note that as soon you say "within an epsilon" you're already on the other side of "not a lot of info" vs "infinite info". So global, local doesn't matter, especially since eg an analytic function is completely determined by it's derivatives at a single point (good ol Taylor's theorem).
> Formally, I'm not sure how to show that's related to the relative difficilties of the two operarions, or if it actually is related in the first place, but intuitively the explanation is appealing.
I wonder if you could relate it to the difference between local and global sections on bundles and connect “global sections don’t always exist” to “global data is harder.”
A team of four PhDs + seven other academics manage to unfold a single protein in an egg white using a "vortex fluid device" to produce a Couette flow, heat treatment, dilution in phosphate-buffered saline, dissolution in ureal, use of recombinant proteins, etc., etc.,
Meanwhile, my four-year old niece can boil a dozen eggs in the time it took me to read their paper.
I think it's still accurate to say unboiling an egg is "difficult"!
Let's say you have a library of functions you know how to integrate and differentiate. Something that happens a lot is that you end up wanting to do integrate or differentiate a product like x -> f(x)g(x) or composition like x -> f(g(x)) of two or more of the functions you know about.
For diffentiation there are two ridiculously powerful theorems which says that if you know how to differentiate a bunch of functions you can also differentiate any product or composition of these functions.
For a random other map there is no reason for this to be the case, integration is essentially "as expected" in that except in some specific circumstances knowing how to integrate f and g doesn't tell you how to integrate their product or composition.
I used this a while back to do an awkward integral that no other CAS was able to do and was able to show up a paper that had claimed there was no closed-form solution.
Unfortunately the answer was in terms of hypergeometric functions and was scarcely more useful than the unevaluated integral. In any case I found Rubi to be very impressivein terms of results.
Digging into the code wasn't much fun, as it's just a colossal Mathematica rules engine, like reading Gradshteyn and Ryzhik, but with square brakets everywhere.
>The SymPy (Symbolic Python) CAS also intends to incorporate Rubi’s integration rules. The code for Rubi is in the sympy/integrals/rubi subdirectory of the SymPy source-code on GitHub.
Has anyone looked at writing a script to transform those rules for yacas? Making yacas 94% as good as Mathematica at integration sounds like a worthy goal considering how easy it is to deploy it.
27 comments
[ 2.5 ms ] story [ 67.4 ms ] threadIt also turns out we can’t even verify, in general, the result of integration:
Suppose you are given two functions, f(x) and G(x), and are told that G(x) is an antiderivative of f(x). So then you let g(x) = G’(x), the derivative of G(x).
Now if G(x) is truly an antiderivative of f(x) then we must have g(x) = f(x) but unfortunately the problem of determining whether two functions are equal is undecidable (a consequence of the halting problem).
Purity doesn't apply to functions, it applies to algorithms which compute functions. In software parlance the terms are often conflated but they are not equivalent. The algorithm which computes a function is in general not unique.
Also, implementing it likely would be a challenge. The Risch algorithm (https://en.wikipedia.org/wiki/Risch_algorithm, https://mathworld.wolfram.com/RischAlgorithm.html) ‘only’ handles “rational functions, radicals, logarithms, and exponential functions”, but may never have been fully implemented (https://mathoverflow.net/questions/374089/does-there-exist-a...)
Formally, I'm not sure how to show that's related to the relative difficilties of the two operarions, or if it actually is related in the first place, but intuitively the explanation is appealing.
https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(diffe...
So it's important to keep in mind the difference between integral and anti-derivative. And note that as soon you say "within an epsilon" you're already on the other side of "not a lot of info" vs "infinite info". So global, local doesn't matter, especially since eg an analytic function is completely determined by it's derivatives at a single point (good ol Taylor's theorem).
I wonder if you could relate it to the difference between local and global sections on bundles and connect “global sections don’t always exist” to “global data is harder.”
Meanwhile, my four-year old niece can boil a dozen eggs in the time it took me to read their paper.
I think it's still accurate to say unboiling an egg is "difficult"!
For diffentiation there are two ridiculously powerful theorems which says that if you know how to differentiate a bunch of functions you can also differentiate any product or composition of these functions.
For a random other map there is no reason for this to be the case, integration is essentially "as expected" in that except in some specific circumstances knowing how to integrate f and g doesn't tell you how to integrate their product or composition.
Unfortunately the answer was in terms of hypergeometric functions and was scarcely more useful than the unevaluated integral. In any case I found Rubi to be very impressivein terms of results.
Digging into the code wasn't much fun, as it's just a colossal Mathematica rules engine, like reading Gradshteyn and Ryzhik, but with square brakets everywhere.
AFAIK, this is the only recent benchmark-type study that compares modern CAS software (Mathematica vs Maxima vs FriCAS vs etc).
https://github.com/corywalker/expreduce
https://12000.org/my_notes/kamek/kamke_differential_equation...