# Time complexity of CAS integration algorithms. Can we always integrate the integrable expressions with guaranteed closed form solutions?

For a given set of operators, if we construct an arbitrary expression that is valid in terms of syntax, and given that,

• the integration is valid (that is, the limit of the sum within the interval as the base tends to infinitesimal place is defined and has finite value). (One example that does not follow this would be $$\lim_{k \rightarrow \infty }\int_0^k \sin(x) \mathrm{d}x$$ I am not talking about the undefined limit here),

• the integration can be simplified to an expression with existing operators (+, -, *, /, $$\sin$$, $$\cos$$, $$\sinh$$, $$\cosh$$ ...). (In this case the case for calculating $$\pi$$ by integrating $$\sqrt{1 - x^2}$$ is discluded), only considering closed form solutions.

(to be more specific, this simplified form of expression should not consist any components constructed by new power series, that is, no limit and error terms used)

is there sufficient methods to guarantee that we can always find the expression that is guaranteed to be closed? And is there a "time complexity" for such algorithms?

Compared with differentiation for which we have quotient rule, chain rule, although we have inverse chain and integration by parts, the transformation is less systematic and if we come up with some valid expressions, for example, the integration of

$$\sin(\sin(\sin(x))$$

with the interval $$(0,3]$$,

then it is defined but requires certain method to simplify. It would be hard to find among books but also hard for CAS ,

If I plug this into Wolfram Alpha

https://www.wolframalpha.com/input/?i=integrate+sin%28sin%28sin%28x%29%29%29 (Links to an external site.)

Other widely used systems, like SageMath, SymPy, and AbstractAlgebra.jl also have troubles finding the symbolic expression.

to derive $$\sin(\sin(\sin(x))$$ is easy, find $$cos(x)cos(sin(x))cos(sin(sin(x)))$$ derive it https://www.wolframalpha.com/input/?i=d+sin%28sin%28sin%28x%29%29%29+%2Fdx however, from this result, wolfram alpha cannot find the origional integrate back https://www.wolframalpha.com/input/?i=integrate+cos%28x%29+cos%28sin%28x%29%29+cos%28sin%28sin%28x%29%29%29+dx

So I have guessed the situation below:

Conversely, if I make a string processing program that randomly generates very long expressions, the CAS will find, if valid, the derivative of which. And the derivatives are formed by the same set (or may be class) of operators. If I then put the found derivative expressions into a CAS, then it MAYNOT be able to find its integration from this expression. In this way it MAY be possible to exhaustively search for new integration rules. Then maybe using meta-programming we put the new rules into the CAS and let it continue to find new rules.

There is still one thing that it depends, that most found methods must be programmable in certain CAS (and that the maintainers had done that).

A type of algorithm can be:

1. generate some random math expressions with strings(using single variable $$x$$, +, -, *, /, $$\sin$$, $$\cos$$, $$\tan$$... and rational numbers),
2. expand, simplify the expression, save it as $$f$$, compute with CAS, its derivative stored as $$\mathrm{D}f$$,
3. use CAS to integrate $$\mathrm{D}f$$ with a given time tolerance $$t$$, if time out, store the $$f$$, $$\mathrm{D}f$$ and status "TIMEOUT", Then we can get a dataset of expressions hard to integrate but have closed form integration expression with finite length

However, as I think further, could there be some "time complexity" of the CAS integration algorithm with respect to the component and structure of the string?

And I did some calculations on CoCalc with these thoughts:

## with CoCalc:

f(x)= 1-x^2

integrate(f, x) x |--> -1/3*x^3 + x

g(x)= sin(sin(sin(x)))

integrate(g,x) x |--> integrate(sin(sin(sin(x))), x) 1 case when integration does not stop in tolerated time h(x) = sin(cos(tan(x+sinh(x-1/log(sinh(x)))))) show(h) x ↦ sin(cos(tan(x+sinh(x−1log(sinh(x))))))

## h1(x) = diff(h,x) timeit(""" h1(x) = diff(h,x) """) 625 loops, best of 3: 85.1 μs per loop show(h1) x ↦ −((cosh(x)log(sinh(x))2sinh(x)+1)cosh(x−1log(sinh(x)))+1)(tan(x+sinh(x−1log(sinh(x))))2+1)cos(cos(tan(x+sinh(x−1log(sinh(x))))))sin(tan(x+sinh(x−1log(sinh(x))))) print(h1) x |--> -((cosh(x)/(log(sinh(x))^2*sinh(x)) + 1)cosh(x - 1/log(sinh(x))) + 1)(tan(x + sinh(x - 1/log(sinh(x))))^2 + 1)*cos(cos(tan(x + sinh(x - 1/log(sinh(x))))))*sin(tan(x + sinh(x - 1/log(sinh(x))))) h_reverse(x) = integrate(h1,x)

RuntimeError Traceback (most recent call last) in () ----> 1 tmp=var("x"); h_reverse = symbolic_expression(integrate(h1,x)).function(x)

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/misc/functional.pyc in integral(x, *args, **kwds) 751 """ 752 if hasattr(x, 'integral'): --> 753 return x.integral(*args, **kwds) 754 else: 755 from sage.symbolic.ring import SR

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/symbolic/expression.pyx in sage.symbolic.expression.Expression.integral (build/cythonized/sage/symbolic/expression.cpp:64013)() 12403 else: # all arguments are gone 12404 R = ring.SR

12405 return R(integral(f, v, a, b, **kwds)) 12406 return integral(self, *args, **kwds) 12407

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/symbolic/integration/integral.pyc in integrate(expression, v, a, b, algorithm, hold) 824 return integrator(expression, v, a, b) 825 if a is None: --> 826 return indefinite_integral(expression, v, hold=hold) 827 else: 828 return definite_integral(expression, v, a, b, hold=hold)

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/symbolic/function.pyx in sage.symbolic.function.BuiltinFunction.call (build/cythonized/sage/symbolic/function.cpp:11837)() 996 res = self.evalf_try(*args) 997 if res is None: --> 998 res = super(BuiltinFunction, self).call( 999 *args, coerce=coerce, hold=hold) 1000

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/symbolic/function.pyx in sage.symbolic.function.Function.call (build/cythonized/sage/symbolic/function.cpp:6917)() 490 (args[0])._gobj, hold) 491 elif self._nargs == 2: --> 492 res = g_function_eval2(self._serial, (args[0])._gobj, 493 (args1)._gobj, hold) 494 elif self._nargs == 3:

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/symbolic/integration/integral.pyc in eval(self, f, x) 89 for integrator in self.integrators: 90 try: ---> 91 return integrator(f, x) 92 except NotImplementedError: 93 pass

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/symbolic/integration/external.pyc in maxima_integrator(expression, v, a, b) 30 expression = SR(expression) 31 if a is None: ---> 32 result = maxima.sr_integral(expression,v) 33 else: 34 result = maxima.sr_integral(expression, v, a, b)

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/interfaces/maxima_lib.pyc in sr_integral(self, *args) 789 """ 790 try: --> 791 return max_to_sr(maxima_eval(([max_integrate],[sr_to_max(SR(a)) for a in args]))) 792 except RuntimeError as error: 793 s = str(error)

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/libs/ecl.pyx in sage.libs.ecl.EclObject.call (build/cythonized/sage/libs/ecl.c:7785)() 804 """ 805 lispargs = EclObject(list(args)) --> 806 return ecl_wrap(ecl_safe_apply(self.obj,(lispargs).obj)) 807 808 def richcmp(left, right, int op):

/ext/sage/sage-8.8_1804/local/lib/python2.7/site-packages/sage/libs/ecl.pyx in sage.libs.ecl.ecl_safe_apply (build/cythonized/sage/libs/ecl.c:5447)() 376 if ecl_nvalues > 1: 377 s = si_coerce_to_base_string(ecl_values(1)) --> 378 raise RuntimeError("ECL says: {}".format( 379 char_to_str(ecl_base_string_pointer_safe(s)))) 380 else:

RuntimeError: ECL says: Console interrupt.

## show(h_reverse(x))

NameError Traceback (most recent call last) in () ----> 1 show(h_reverse(x))

NameError: name 'h_reverse' is not defined For simple cases, integration does work but takes relatively more time H(x) =sin(sin(sin(x))) show(H) x ↦ sin(sin(sin(x)))

p1 = plot(H,(x,-5,5)) show(p1)

H1(x) = diff(H,x) show(H1) x ↦ cos(x)cos(sin(x))cos(sin(sin(x)))

H1reverse(x) = integrate(H1,x) show(H1reverse) x ↦ sin(sin(sin(x)))

differentiationCode = """ H1(x) = diff(H,x) """ integrationCode = """ H1reverse(x) = integrate(H1,x)

""" timeit(differentiationCode) 625 loops, best of 3: 86 μs per loop timeit(integrationCode) 625 loops, best of 3: 714 μs per loop G(x) = sin(sin(x)+1) plot(G,(x,-5,5)) show(G) G1 = diff(G,x) show(G1) Greverse =integrate(G1,x) show(Greverse) x ↦ sin(sin(x)+1)

x ↦ cos(x)cos(sin(x)+1)

x ↦ sin(sin(x)+1)

show(plot(G,(x,-5,5))) show(plot(G1,(x,-5,5))) timeit(""" G1 = diff(G,x) """) 625 loops, best of 3: 10.6 μs per loop timeit(""" Greverse =integrate(G1,x) """) 625 loops, best of 3: 426 μs per loop

show(G) x ↦ sin(sin(x)+1)

Causation of failure J(x) = sin(cos(tan(x))) plot(J,(x,-5,5))

J1(x) = diff(J,x) show(J1) x ↦ −(tan(x)2+1)cos(cos(tan(x)))sin(tan(x))

plot(J1,(x,-5,5))

Jreverse = integrate(J1,x)

show(Jreverse) x ↦ sin(cos(tan(x)))

timeit("""J1 = diff(J,x)""") 625 loops, best of 3: 20.1 μs per loop timeit("""Jreverse = integrate(J1,x)""") 125 loops, best of 3: 1.37 ms per loop

y(x)=1/(2+1/x) iy=integrate(y,x) show(iy) x ↦ 12x−14log(2x+1)

plot(iy+,(y,-5,5)) verbose 0 (3635: plot.py, generate_plot_points) WARNING: When plotting, failed to evaluate function at 90 points. verbose 0 (3635: plot.py, generate_plot_points) Last error message: 'can't convert complex to float'

y1(x)=2*x+log(x) plot(y1,(x,-5,5)) verbose 0 (3635: plot.py, generate_plot_points) WARNING: When plotting, failed to evaluate function at 100 points. verbose 0 (3635: plot.py, generate_plot_points) Last error message: 'can't convert complex to float'

Modern serious CASes do have an algorithm (in addition to heuristics) to compute antiderivatives. The name's Risch algorithm. It is really difficult to even start explaining due to both

• its sheer complexity (no complete implementations exist as of today even if you don't count stuff like constant problem that is an open mathematical problem, and the lack of knowledge regarding transcendence degree of certain constants like pi+e),
• its immense prerequisites (a good math postgraduate would probably understand the basics)

If you're curious, you can try reading Manuel Bronstein's Symbolic Integration Tutorial, a rather advanced article that outlines what the modern CASes are supposed to do. Unfortunately, most CASes fail at some of his examples even now, more than 20 years after his tutorial was published.

Regarding the integrand $$f(x)=\sin(\sin(\sin(x)))$$, modern CASes easily prove that the antiderivative is not elementary. In fricas, for example, if the integral was proven non-elementary, the output will have the input integral with the free variable replaced with %A. If, on the other hand, the system failed to prove that the antiderivative is not an elementary function, the output usually contains the error message.

Here's an example of an integral that fricas fails to prove non-elementary:

integrate(sqrt(x+sin(x)),x)
>> Error detected within library code:
integrate: implementation incomplete (has polynomial part)


...although $$\int\sqrt{x+\sin(x)}\mathbb{d}x$$ is indeed non-elementary.

As for the time complexity, indeed, certain parts of the general algorithm are very time-consuming, for example, certain symbolic calculations in rings where the factorization is not unique.

There indeed are big cached tables of antiderivatives, and sometimes the general Risch algorithm is not invoked, but no heuristics could replace the generality of an algorithm, even if it's implementation is not complete.