How do experts mentally classify indefinite integrals?

Integration is as much an art as a science. Someone who is an expert looks at an indefinite integral and classifies it in a different way than someone who is a beginner. E.g., the beginner may just say, "This is in chapter 7, and chapter 7 is on trig substitutions, so obviously I need to do a trig substitution." I'm at a much higher level than that, but a much lower level than some people on this site. This is similar to the way in which a good chess player looks at a board and say "That's a Ruy Lopez," while a patzer like me just goes, "Uh, it's a chess position."

Computer software obviously changes how people approach these things in practice, and makes the traditional skills less necessary. But just as a good computer algorithm for playing chess or translating Russian to English may be nothing like the way a human experts does these things, the existence of an algorithm such as the Risch algorithm may or may not have anything to do with how a human would approach the problem.

An important question is how to determine whether there is no hope of doing an integral using elementary functions. The Risch algorithm provides a decision procedure for this, but I suspect that human experts use a completely different set of heuristics. I just have a small catalog of examples that I know are impossible, like $\int e^{-x^2} dx$, and when I see a form such as $\int e^{-x^2+x} dx$ that can obviously be translated into one of those, I know it can't be done. But, e.g., it was not at all obvious to me that $\int e^x\tan x d x$ was impossible; I figured I might be able to do something by rewriting the tangent using complex exponentials. In that example, one can resort to computer software to determine that it equals a hypergeometric function, and since we know a hypergeometric function can't be expressed using elementary functions (except for certain special cases), we determine that the integral can't be. But presumably experts have some insight into this problem that allows them to determine that it's impossible without recourse to a computer or an old-fashioned paper table of integrals such as Gradshteyn and Ryzhik.

There are also cases where an algorithm works in theory, but in practice it's the wrong approach. E.g., the computer software I've tried out on $\int dx/(x^{10000}-1)$ all chokes, presumably because it tries to do a partial-fraction decomposition by brute force.

The examples of $\int e^x\tan x d x$ and $\int dx/(x^{10000}-1)$ both happen to be expressible in terms of hypergeometric functions. Do experts often work by having a mental catalog of special functions such as Erf and hypergeometric functions, and recognizing forms of integrals that will evaluate to those? Maybe one of the differences between them and me is that their catalogs are simply bigger than mine. If so, what is in their catalogs?

Would anyone who is an expert be willing to try to sketch out their own mental process for classifying integrals?

Solution 1:

Many of the well-known heuristics were catalogued and employed in heuristic symbolic integration algorithms, especially in the period of computer algebra that predated the discovery of the decision procedures for integrating elementary functions (Risch, Bronstein, etc). For examples of such work, see Joel Moses, Symbolic Integration: the stormy decade and his MIT thesis Symbolic Integration, 1967. Later work can be located by chasing references to these influential early publications.

The analogy with chess only goes so far, because many (but not all) of the integration heuristics are related to known algorithms, whereas the same cannot be said for chess. For example, computer reanalysis of the classical human-derived endgame strategies yields the surprising result that optimal play often violates human heuristics. Further, optimal play may be so complex in general that it is beyond the grasp of mere mortals. Grandmasters have had severe difficulties playing against these endgame databases. Optimal play is so complex that in one case a recognized endgame expert (Roycroft) was able to comprehend a certain endgame database only with enormous effort and the aid of automated inductive-learning algorithms. See here for further discussion.