9

I asked this question on MSE here.

I recently learned that there are many very large numbers that have been defined, such as $\operatorname{TREE}(3)$ and many others that are too big to be written down.

What made me interested is the idea that there is a function that take some finite and small number like $3$ to an absolute beast of a number.

So I wonder if there is some function with an elementary antiderivative that we know its antiderivative is too large to be written down without any shorthand notation like $\sum\limits_{n \in J} c_n f_n(x)$ st that $J$ is a finite set and $f_n $ is some combinations of elementary functions , although we can write down the function itself.

Or in other words: How complicated can an elementary antiderivative get? Is there some example of such functions (examples of functions with elementary antiderivatives that are too big to be written down, although we can write down the functions themselves)? If not, is there a proof why elementary antiderivatives can't get that complicated?

pie
  • 139
  • 8
    Something like $\int \sin^n dx$ for large n should result in lots and lots of terms when calculating it in the standard way of repeated partial integrations, but I have no idea how to prove that there is no nicer closed form. – mlk Jan 22 '24 at 10:29
  • 8
    It might be possible to extract an upper bound for the possible length from the Risch algorithm – Command Master Jan 22 '24 at 10:39
  • 13
    I agree with Command Master's comment. See this MO question, and in particular the paper by Daniel Schultz, for some indication of how complicated an elementary antiderivative can get. Offhand, I don't know an upper bound, but my impression is that the most computationally expensive part is some kind of Gröbner basis calculation. So I'd guess that there's a doubly exponential upper bound. Certainly nothing like TREE or even Ackermann. – Timothy Chow Jan 22 '24 at 14:01
  • 3
    I think it is also important in this regard to consider how one measures the complexity of the resulting antiderivatives. If one employs the Kolmogorov complexity as a measure, on might be interested in the following article: https://link.springer.com/chapter/10.1007/978-3-642-21875-0_9 – Max Muller Jan 23 '24 at 16:11
  • 8
    I think that at this point it would be best if you stopped the frequent minor edits. If you can't get the question right after 11 edits, then I would stop and reflect about what exactly you're trying to get from it. – Andy Putman Jan 23 '24 at 19:11
  • @AndyPutman most of them are grammar edits I am not good t english and so I am not very sure want to use to write this (for example do I use "how much complicated" or "how complicated") , you will notice many of my question on MSE or HSM have very bad grammar or spelling, If it is annoying I will not edit this question again

    I apologise for this

     – pie Jan 23 '24 at 19:15
  • 3
    @pie: I think it's best to not make so many edits. Each edit pushes the question to the top of the queue again, so it is unfair to other people who are trying to get attention for their questions. – Andy Putman Jan 23 '24 at 19:20
  • @AndyPutman Ok I will not edit this again. I am sorry for that. – pie Jan 23 '24 at 19:22
  • 1
    Your link went to a comment on your MSE question, whereas it seemed that you meant to link to the question itself. I edited accordingly. – LSpice Jan 23 '24 at 19:30
  • 4
    @TimothyChow Won't you get faster growth just because the definition of elementary function involves composition so we can write the integral of $\frac{x^n-1}{x-1}$ where $n$ is a tower of exponentials of length $m$ in $O(m)$ characters? But it's probably not possible to express the integral with fewer than $n$ characters. – Will Sawin Feb 01 '24 at 17:26
  • 2
    @WillSawin Hmmm...good point! That does seem to be correct. I still don't expect that anything like Ackermann is possible, though. – Timothy Chow Feb 02 '24 at 01:34
  • 1
    I see no reason to assume long solutions for short elementary integrands with low coefficients. $\int dx/(2 + sin^5) $ is short for example. Afterall if the number of compositions and products are small, we probably do not need to use many tricks. Especially if we allow hypergeo and other special functions and sums over zero's of a given function. Show me a counterexample !? – mick Feb 03 '24 at 22:55

0 Answers0