7
$\begingroup$

Sometimes a fairly simple symbolic integral problem has an extremely complicated answer, as @Nasser showed in his superb answer to this question: One of the moderately difficult integrals has a solution that comprises an astounding 57,000 leafs in its simplest symbolic form!

I sometimes speak with "pure" mathematicians who are reluctant or skeptical of using computer algebra systems such as Mathematica thinking (incorrectly) that such systems somehow degrade or replace mathematical knowledge and expertise. (Such systems do not... particularly when used properly. Quite the contrary.)

When we discuss indefinite integration (for example), they say there is value in students and researchers alike recognizing which integration technique should be used for a given problem (integration by parts, partial fractions, trigonometric substitution, ...), and trying them out. Well, I guess there is.

But integration problems can sometimes be very difficult to "read" in this way. And sometimes two integrals that look "almost" the same require very different approaches and lead to very different symbolic answers.

I'd like to illustrate this fact.

Hence my problem/request:

I'd like to find a "fairly simple" symbolic indefinite integral problem that leads to a "fairly simple" answer... BUT, if the problem is altered "ever so slightly" the answer is extremely long and complicated.

As with the linked problem above, let us quantify "simplicity" of an expression by the leaf count of the expressions' representation (LeafCount[]). Let us call the original integral problem PROBLEM 1 and its solution SOLUTION 1, and likewise for the altered problem PROBLEM 2 and SOLUTION 2.

A reasonable merit function to maximize is then:

$$\frac{|LC[Solution 2] - LC[Solution 1]|}{|LC[Problem 2] - LC[Problem 1]|}$$

where LC represents the leaf count.

Note that PROBLEM 2 should be typographically close to PROBLEM 1... that is, a small alteration of it. I'm not quite sure how to express this in a crisp quantitative form, so I suppose this is part of the problem too.

Imagine we find a PROBLEM 1 that has a simple SOLUTION 1, but that merely adding an exponent to a single term leads to a PROBLEM 2 with extraordinarily complicated and long SOLUTION 2.

That would be of interest and value as it would strongly suggest that computer algebra systems will always be better than unaided mathematicians in finding the right integration technique... and that students will be wasting time even trying to find the "right" integration technique and testing it out.

$\endgroup$
2
  • $\begingroup$ "degrade or replace mathematical knowledge and expertise" a lot of modern papers would be impossible without systems like Coq. Another example is recent measure of irrationality of Pi, that would be impossible without Maple. sites.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/… and of course recent new algorithms of matrix multiplication would be impossible wothout AI system Alphatensor. $\endgroup$ Feb 24, 2023 at 20:50
  • 2
    $\begingroup$ Exactly. But I'd argue even more strongly... that practicing math (not only forefront research math) is enhanced in mathematical understanding through symbol manipulation software. Someday (soon, I hope) it will be fully integrated into nearly all "pure" math courses. $\endgroup$ Feb 24, 2023 at 23:01

3 Answers 3

2
$\begingroup$

Leafcount might not be the best measure here. Why? because two expressions with very small difference can have the same leafcount. For example

LeafCount[Sin[x]^2]
LeafCount[Sin[x]^3]

Both have leaf count of 4. and

LeafCount[Integrate[Sin[x]^2, x]]
LeafCount[Integrate[Sin[x]^3, x]]

Give 14 and 15. So using the above metric, this will give $\infty$ for both, since 4-4=0 and we are dividing by leafcount difference of the integrands.

The following solution uses DamerauLevenshteinDistance see also wikipedia

is a string metric for measuring the edit distance between two sequences.

The above is used to find distance between the integrands when they are in string form (with all spaces removed and in InputForm). Then those integrands with distance of no more than 1 apart to use for the rest of the solution.

DamerauLevenshteinDistance["Sin[x]^2", "Sin[x]^3"]
(*1*)

Other distance measures are available.

I tried few and found the above to work best. But this can be easily changed if someone suggests a better one to use. I am only familiar with sequence alignments ones and not strings distance measures.

The metric will now be just the leafCount difference between the anti-derivatives of each. No division is needed since distance is always 1 between the two integrands.

Notice that distance of zero implies the same exact integrand.

By taking a distance of two for example, More variations will result between the integrands.

Results for Damerau Levenshtein Distance of one

The following was generated by running a Mathematica program on 85,000 integrals in the independent CAS integration SQL database (available on the internet) which finds those problems with distance of 1 which also has leafcount difference over 500.

The run time is O(n^2) since it has to compare each integral with all the others.

The above choice of 500 is arbitrary but used to limit the table size below.

Important The output used for each problem to compare against is the smallest one generated by either Mathematica, Rubi or the optimal one as recorded. This is done automatically now.

Selected examples

Example 1

Mathematica graphics

Example 2

Mathematica graphics

Example 3

Mathematica graphics

Example 5

Mathematica graphics

Example 5

Mathematica graphics

Example 6

Mathematica graphics

Current result

The full table is too large to put here.

Plain text format of the table, and notebook and PDF are in this folder to download.

272 integrals were found which integrands have distance 1 between them but the anti-derivatives sizes are more than 500 in leaf count apart.

Here is partial screen shot of the table

(click to enlarge)

enter image description here

Results for Damerau Levenshtein Distance of two

The following is result using distance two. There are 902 integrals found with leaf count of more than 500 difference in the output while the integrand are only distance 2 apart.

The full table is too large to put here.

Plain text format of the table, and notebook and PDF are in this folder to download.

Some examples

Example 1

Example 2

Mathematica graphics

Here is partial screen shot of the table

(click to enlarge)

enter image description here

$\endgroup$
1
  • $\begingroup$ Wow... another superb and "more-than-asked-for" answer from Nasser! ($+1$, $\checkmark$). $\endgroup$ Feb 24, 2023 at 15:51
5
$\begingroup$

This is an extended comment.

Clear["Global`*"]

f[x_] := Sin[x];

funcs = {f[x], f[x + a], f[a/x], f[x^a], f[a^x]};

list = Inactive[Integrate][#, x] & /@ funcs;

lcProbl = LeafCount /@ list

(* {5, 7, 9, 7, 7} *)

lcSoln = LeafCount /@ Activate[list]

(* {4, 12, 18, 62, 9} *)

Prepend[
  SortBy[
   Thread[{
     Prepend[Abs[Rest[lcSoln] - First[lcSoln]]/
       Abs[Rest[lcProbl] - First[lcProbl]], 1], funcs,
     Activate[list]}],
   First],
  {"metric", "function", "Integral"}] //
 Grid[#, Frame -> All] &

enter image description here

Note that with the proposed metric, a relatively simple expression like -Cos[a] Cos[x] + Sin[a] Sin[x] scores lower than expressions involving complicated higher transcendental functions (e.g., SinIntegral, CosIntegral).

$\endgroup$
1
  • $\begingroup$ Thanks for your quick reply and helpful comment ($+1$).... the right idea indeed. I was astounded by @Nasser's solution to the linked problem, so I'm extremely confident that we can find a far more extreme case. But you've shown an algorithmic way forward... Again, thanks! $\endgroup$ Feb 20, 2023 at 18:42
3
$\begingroup$

In[31]:= LeafCount[1/(1 + Sqrt[1 - Cos[x]^6])] - LeafCount[1/(1 + Sqrt[1 - Cos[x]])]

Out[31]= 2

In[32]:= LeafCount[Integrate[1/(1 + Sqrt[1 - Cos[x]^6]), x]] - LeafCount[Integrate[1/(1 + Sqrt[1 - Cos[x]]), x]]

Out[32]= 20513

In[33]:= metric = 20513/2.

Out[33]= 10256.5

$\endgroup$
8
  • 1
    $\begingroup$ Hello; if you try the above in Rubi Integrator, you will get much different result. instead of 20513 it will be 194. The issue here seems that Mathematica Integrate itself is not producing optimal antiderivative. !Mathematica graphics $\endgroup$
    – Nasser
    Feb 21, 2023 at 1:09
  • $\begingroup$ Also, if you apply Simplify on the result of Mathematica, 20513 will drop down to 4027. I am not sure if one is allowed to use Simplify on the result here. But this can make big difference. !Mathematica graphics $\endgroup$
    – Nasser
    Feb 21, 2023 at 1:28
  • $\begingroup$ Yes... you're allowed to use--and indeed should use--FullSimplify. $\endgroup$ Feb 21, 2023 at 1:39
  • $\begingroup$ @Nasser Both Simplify and FullSimplify are taking too long for me but I take your word that they decrease LeafCount. Rubi does not calculate the integral; it returns a result that contains other integrals left unevaluated. $\endgroup$
    – ulvi
    Feb 21, 2023 at 2:33
  • $\begingroup$ Actually Simplify on V 13.2 took about 1 minute for me, but may be my PC is fast. FullSimplify is not practical since it can take very very long time, yes. But if you try Simplify you will see (it should not take more than 2-3 minutes). You are right about Rubi's result. I did not look at it when I checked LeafCount, I assumed it can do it. Ok, we can forget about Rubi result here. $\endgroup$
    – Nasser
    Feb 21, 2023 at 2:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.