4 ms·

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 b

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.

mkl 2y ago
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.
chongli 2y ago
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).
- carbotaniuman 2y ago
  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.
  - chongli 2y ago
    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.
  - kccqzy 2y ago
    Just determining the equality of two real numbers is difficult.
  - xigoi 2y ago
    The problem is that what you’re comparing are not functions, but representations of functions.
- Someone 2y ago
  > There is no general algorithm to symbolically compute all integrals Also, implementing it likely would be a challenge. The Risch algorithm (https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm, https://mathworld.wolfram.com/RischAlgorithm.html 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-complete-implementation-of-the-risch-algorithm https://mathoverflow.net/questions/374089/does-there-exist-a...)
GrantMoyer 2y ago
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.
- almostgotcaught 2y ago
  It's not that simple https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra) 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).
- 6gvONxR4sf7o 2y ago
  > 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.”
barrenko 2y ago
What is so difficult about unfrying an egg :D.
- ValentinA23 2y ago
  nothing https://www.livescience.com/49610-scientists-unboil-egg.html https://www.livescience.com/49610-scientists-unboil-egg.html
  - CoreformGreg 2y ago
    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"!
eigenket 2y ago
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.
- deleted 2y ago
  [deleted]
namibj 2y ago
Technically division is asymptotically as cheap as multiplication, but in practice you can't really utilize this.

mkl 2y ago

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.

chongli 2y ago

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

carbotaniuman 2y ago
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.
- chongli 2y ago
  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.
- kccqzy 2y ago
  Just determining the equality of two real numbers is difficult.
- xigoi 2y ago
  The problem is that what you’re comparing are not functions, but representations of functions.
Someone 2y ago
> There is no general algorithm to symbolically compute all integrals Also, implementing it likely would be a challenge. The Risch algorithm (https://en.wikipedia.org/wiki/Risch_algorithm https://en.wikipedia.org/wiki/Risch_algorithm, https://mathworld.wolfram.com/RischAlgorithm.html 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-complete-implementation-of-the-risch-algorithm https://mathoverflow.net/questions/374089/does-there-exist-a...)

GrantMoyer 2y ago

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.

almostgotcaught 2y ago
It's not that simple https://en.m.wikipedia.org/wiki/Liouville%27s_theorem_(differential_algebra) 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).
6gvONxR4sf7o 2y ago
> 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.”

barrenko 2y ago

What is so difficult about unfrying an egg :D.

ValentinA23 2y ago
nothing https://www.livescience.com/49610-scientists-unboil-egg.html https://www.livescience.com/49610-scientists-unboil-egg.html
- CoreformGreg 2y ago
  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"!

eigenket 2y ago

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.

deleted 2y ago
[deleted]

namibj 2y ago

Technically division is asymptotically as cheap as multiplication, but in practice you can't really utilize this.