The Valhalla of special functions

[leblon]

Thus the dilogarithm is one of the simplest non-elementary functions one can imagine. It is also one of the strangest. It occurs not quite often enough, and in not quite an important enough way, to be included in the Valhalla of the great transcendental functions—the gamma function, Bessel and Legendre- functions, hypergeometric series, or Riemann’s zeta function.

Don Zagier

Comments

[chaource.livejournal.com]

A while ago I was studying the computational methods used in computer algebra systems, and I found an interesting phenomenon: Special functions can be classified according to the asymptotic complexity of the numerical calculation of their values to high precision.

The asymptotic complexity is measured in the number of high-precision multiplications. For instance, if we want to compute sqrt(3) with P decimal digits of precision (for very large P), we need to carry out O(ln P) multiplications of P-digit numbers. (The fastest computation is done using Newton's method.) This complexity is denoted by O(ln P) M(P), where M(P) is the number of operations required to multiply two P-digit integers. (The best asymptotic method for that is P (ln P)^2 or something like that.)

If we want to compute cos(sqrt(3)), we still need only O(ln P) multiplications. So cosine and square root are "equally complicated". The same holds for exp, ln, arctan and other elementary functions.

Now, as far as I remember, the Bessel function has the same asymptotic complexity as elementary functions: O(ln P) M(P). However, the Gamma function and Riemann's Zeta function have much higher complexity. For instance, Riemann's Zeta function is O(P/ln P) M(P). Catalan's constant has complexity O(ln P)^2 M(P).

Euler's constant has complexity O(ln P) M(P ln P). The same complexity holds for Euler's Gamma function on rational arguments, e.g. Gamma(1/5). However, the Gamma function on general arguments, e.g. Gamma (sqrt(2)), has complexity O(P) M(P).

So, in this sense, not all functions are equal in the "Valhalla of transcendental functions".

[aron-turgenev.livejournal.com]

О, интересно, а ссылку не дадите?

[leblon.livejournal.com]

Sure:

http://people.mpim-bonn.mpg.de/zagier/files/doi/10.1007/978-3-540-30308-4_1/fulltext.pdf

[aron-turgenev.livejournal.com]

Merci.

[leblon.livejournal.com]

Интересно. Но это зависит от довольно субъективных вещей, типа "какие алгоритмы для вычисления функции известны человечеству", так?

[38irtimd.livejournal.com]

интересно, можно ли это наблюдение как-то применить к, например, Schanuel's conjecture (https://en.wikipedia.org/wiki/Schanuel%27s_conjecture). Её версии можно формулировать не только для экспоненты, но и для других трансцендентных функций, это довольно активная область сейчас, правда гипотез там больше, чем доказательств.

[chaource.livejournal.com]

I think, yes, it does. I haven't seen any proofs that, say, sqrt(2) cannot be computed faster than O(ln P) M(P). This is the best we know. Maybe there are some proofs for some such functions, but I imagine it would be extremely difficult to prove that for a complicated special function.

[roma.livejournal.com]

I also noticed this curious passage -- but I am not sure how to read the metaphor. To get to Valhalla they must have died in battle -- I wonder who was fighting them?