💻 computer science

Exhaustive Symbolic Integration: Integration by Differentiation and the Landscape of Symbolic Integrability

This paper introduces Exhaustive Symbolic Integration (ESI), a method that enumerates functions to map the landscape of symbolic integrability, revealing that the choice of operator basis critically determines integrability rates and enabling the discovery of novel closed-form antiderivatives that elude existing computer algebra systems.

Original authors: Harry Desmond

Published 2026-05-07

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Harry Desmond

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a librarian trying to organize a massive library of mathematical recipes. In this library, every recipe is a "function" (a mathematical expression like $x^2 + \sin(x)$ ).

Usually, mathematicians have a very powerful tool called Differentiation. It's like a machine that takes any recipe and instantly tells you its "rate of change" (its derivative). This machine works perfectly every time; it's algorithmic and reliable.

Integration, however, is the reverse process. It's like trying to guess the original recipe just by looking at the rate of change. This is much harder. There is no single machine that can solve every integration problem, and sometimes, the original recipe simply doesn't exist in the language we are using.

The Big Question

The authors of this paper asked a simple but profound question: "If we pick a random recipe from our library, how likely is it that its original version (the antiderivative) is also in our library?"

To answer this, they invented a new method called Exhaustive Symbolic Integration (ESI).

The Method: "Guessing by Checking"

Instead of trying to solve integrals one by one (which is what standard computer programs do), the authors decided to build a complete catalog of every possible mathematical recipe up to a certain size (complexity).

Build the Library: They generated millions of unique mathematical expressions using different sets of building blocks (operators like addition, multiplication, exponents, logs, and trig functions).
Differentiate Everything: They ran every single one of these millions of recipes through the differentiation machine.
The Match: They then asked: "Does the result of this differentiation match any other recipe already in our library?"
- If Yes: The library is "closed" under integration for that recipe. We found the answer.
- If No: The answer exists, but it's too complex or uses different tools than our library allows.

By doing this for millions of recipes, they calculated an "Integrability Fraction" ( $\rho$ ). This is simply the percentage of recipes in their library that have a "partner" (an antiderivative) also sitting in the same library.

The Surprising Discoveries

1. The "Logarithm" Superpower
The authors tested five different sets of building blocks. They found that adding the Logarithm ( $\log$ ) to the mix was a game-changer.

Analogy: Imagine a set of Lego bricks. If you only have basic blocks, you can build some cool things, but you can't build a castle. If you add a specific "special" brick (the Logarithm), suddenly you can build a castle out of the same number of bricks.
The Result: When they added the Logarithm, the percentage of solvable integrals jumped by a factor of 3. It made the library much more "complete."

2. The "Trigonometry" Trap
They expected Sine and Cosine to be just as helpful as Logarithms because they are famous for being "closed" (the derivative of sine is cosine, and vice versa).

The Reality: They weren't. The integrability fraction for trigonometric functions was much lower, similar to the basic sets.
Why? The "Chain Rule" (a mathematical rule for nested functions) acts like a complexity monster. When you differentiate a trig function inside another function, it multiplies the complexity, pushing the answer out of the library's size limit.

3. The "Peak" at Complexity 6
For the libraries containing Logarithms, the authors noticed a strange bump. The integrability fraction didn't just go down as the recipes got bigger; it actually rose to a peak when the recipes had about 6 "steps" (complexity level 6) before falling again.

Analogy: It's like a dance floor. At first, as the music gets faster (complexity increases), more people can join the dance (integrability goes up). But eventually, the music gets too fast, and people start tripping over each other (integrability goes down). The Logarithm seems to keep the dance floor open a little longer.

Beating the Computers

The authors also used their method as a detective tool to find integrals that even the world's best computer algebra systems (like Mathematica, SymPy, and others) couldn't solve.

The Challenge: They took their massive catalog and checked which integrals the super-computers failed to solve.
The Result: They found three specific integrals that resisted all six major computer systems tested.
- These integrals looked like a mix of square roots and exponential towers (e.g., $\sqrt{x} + e^x$ ).
- The computers got stuck because the answer required a very specific, compact form that their standard algorithms didn't look for.
- ESI found the answer simply because it had already "seen" the answer in its exhaustive catalog.

The Takeaway

This paper doesn't just say "we solved some hard math problems." It reveals the landscape of what is possible.

The Landscape: It shows that whether a math problem is solvable depends heavily on which tools (operators) you allow yourself to use.
The Logarithm: It is a "super-tool" that makes the world of integrable functions much larger.
The Limit: As problems get more complex, the chance of finding a simple answer drops, because the "derivatives" grow faster than the "functions" themselves.

In short, the authors built a massive map of the mathematical universe. They found that while the map gets emptier as you go further out, adding a "Logarithm" bridge makes the territory much richer and easier to navigate. They also found a few hidden caves (the three unsolved integrals) that the standard maps missed.

Technical Summary: Exhaustive Symbolic Integration and the Landscape of Symbolic Integrability

Problem Statement
While differentiation is algorithmic and universally computable for elementary functions via the chain and product rules, integration lacks a universal algorithm. Although the Risch algorithm (1969), grounded in Liouville's theorem (1835), provides a decision procedure for determining if an elementary function possesses an elementary antiderivative, it does not address a fundamental structural question: within a specific class of symbolic expressions, how prevalent is integrability? Specifically, if a function is drawn randomly from a well-defined symbolic grammar with bounded complexity, what is the probability that its antiderivative can be expressed within the same grammar? Previous work has focused on generating random expressions for machine learning training or benchmarking existing Computer Algebra Systems (CAS) on curated test sets, but no study has systematically measured the "integrability fraction" as a function of complexity and operator basis.

Methodology: Exhaustive Symbolic Integration (ESI)
The authors introduce Exhaustive Symbolic Integration (ESI), a method that enumerates all distinct symbolic functions up to a given complexity $k$ within a specified operator basis and determines which admit closed-form antiderivatives within that same class. The methodology proceeds as follows:

Function Space Construction: Using Exhaustive Symbolic Regression (ESR), the authors generate all expression trees with at most $k$ nodes for five distinct operator bases. Complexity is defined by the number of nodes in the tree. The bases studied range from minimal rational operations to sets including exponentials, logarithms, and trigonometric functions.
Deduplication: To ensure the integrability fraction is not inflated by syntactic variations of the same mathematical function, the authors employ a two-stage deduplication process:
- Symbolic Simplification: Expressions are converted to SymPy objects and simplified.
- Numerical Fingerprinting: To catch duplicates missed by symbolic simplification, expressions are evaluated at $N=60$ random points with fixed parameter values. The resulting values are rounded and hashed via MD5 to create a compact fingerprint. Functions with identical fingerprints are treated as equivalent.
Differentiation and Mapping: Each function $F$ in the set $\mathcal{F}_{\le k}$ is differentiated to produce $F'$ . The fingerprint of $F'$ is checked against the set of fingerprints of all functions in $\mathcal{F}_{\le k}$ .
Integrability Fraction ( $\rho(k)$ ): The fraction of functions whose derivatives (and thus whose antiderivatives, by definition of the inverse map) remain within the set is calculated as:
$\rho(k) = \frac{|\{F \in \mathcal{F}_{\le k} : \text{hash}(F') \in \text{hash}(\mathcal{F}_{\le k})\}|}{|\mathcal{F}_{\le k}|}$
CAS Comparison: The method is deployed as an integration algorithm by searching the precomputed catalogue for primitives matching target integrands. These results are compared against six CAS engines (SymPy, Mathematica, RUBI, FriCAS, Maxima, Giac) using various strategies and timeouts to identify integrals that resist standard algorithms.

Key Results
The study analyzes over $10^6$ unique functions across five operator bases up to complexity $k=10$ .

Declining Integrability at High Complexity: For bases with high-complexity coverage (e.g., core_maths, ext_maths, trig_maths), $\rho(k)$ declines as $k$ increases. For instance, core_maths drops from $\sim5.5\%$ at $k=7$ to $3.5\%$ at $k=10$ . This occurs because the space of distinct derivative forms grows faster than the function space itself.
The Logarithm Effect: The inclusion of the logarithm operator dramatically alters the landscape. The ext_log_maths and core_log_maths bases exhibit a $\rho(k)$ $ρ (k)$ roughly 2.5 to 3.6 times higher than their non-log counterparts. Furthermore, these bases display a distinct non-monotonic peak at $k=6$ $k = 6$ (reaching $\sim11.6\%$ $\sim 11.6%$ for ext_log_maths and $19.2\%$ $19.2%$ for core_log_maths).
- Mechanism: The derivative of a logarithm, $d/dx[\log(f)] = f'/f$ , produces rational forms that overlap efficiently with the existing function catalogue. In contrast, the derivative of an exponential, $d/dx[\exp(f)] = f' \exp(f)$ , introduces a new exponential factor that often pushes the complexity beyond the enumeration limit, reducing the probability of finding a match.
Trigonometric Independence: The trig_maths basis (sin/cos) does not show the same elevated integrability as the log bases. Despite the closed orbit of sin/cos under differentiation, the chain rule introduces multiplicative factors ( $f'$ ) that drive rapid complexity growth, offsetting the closure benefits.
Novel Integrals and CAS Limitations: ESI successfully identifies three integrals that resist all six tested CAS engines under all strategies. These integrals share a structural pattern: a square-root algebraic extension coupled to a transcendental tower (e.g., $e^x$ $e^{x}$ , $e^{-x}$ $e^{- x}$ , or $x^x$ $x^{x}$ ) in a way that cannot be undone by closed-form substitution. Examples include:
- $\int (2x+1)e^{\sqrt{x}+e^{-x}} dx = 2\sqrt{x}e^{\sqrt{x}+e^{-x}}$
- $\int (2x+1)e^{\sqrt{|x-e^{-x}|}} dx$
- $\int x^{x-3/2}(1-x-x\log x) dx = 2\sqrt{|x-x^x|}$
  Additionally, ESI finds simpler antiderivative forms than CAS in a significant portion of cases, often saving substantial node counts by preferring factored or nested representations over expanded forms.

Significance and Claims
The paper claims that the landscape of symbolic integrability is primarily shaped by the choice of operators rather than being a uniform property of elementary functions. The introduction of the logarithm operator creates a "closure density" that significantly boosts the probability of finding an antiderivative within a bounded complexity class.

The authors position ESI not as a competitor to general-purpose CAS for all integration tasks, but as a tool for exhaustive structural coverage. Its significance lies in:

Systematic Discovery: It can systematically discover integrable forms, including novel ones, that elude current Risch implementations and heuristic methods.
Quantitative Analysis: It provides the first quantitative measurement of the integrability fraction $\rho(k)$ , revealing how specific operators promote or demote closure under integration.
Algorithmic Gap Diagnosis: By identifying integrals that resist even the most complete Risch implementations (like FriCAS), ESI highlights specific structural gaps in current computer algebra systems, particularly regarding algebraic extensions over exponential-logarithmic towers.

The authors note that their quantitative results (such as the specific location of the $k=6$ peak) are dependent on the specific expression grammar and complexity metric used (node count), but the broader trends—logarithmic enhancement and high-complexity decline—are robust features of the tested grammars.