Double exponential function

A double exponential function is a constant raised to the power of an exponential function. The general formula is , which grows even faster than an exponential function. For example, if a = b = 10:

* f(−1) ≈ 1.26
* f(0) = 10
* f(1) = 10¹⁰
* f(2) = 10¹⁰⁰ = googol
* f(3) = 10¹⁰⁰⁰
* f(100) = googolplex.

Factorials grow faster than exponential functions, but much slower than double-exponential functions. The hyper-exponential function and Ackermann function grow even faster. See Big O notation for a comparison of the rate of growth of various functions.

The inverse of a double exponential function is a double logarithm.

Doubly exponential sequences

Aho and Sloane observed that in several important integer sequences, each term is a constant plus the square of the previous term, and show that such sequences can be formed by rounding to the nearest integer the values of a doubly exponential function in which the middle exponent is two.[1] Integer sequences with this squaring behavior include

* The Fermat numbers

* The harmonic primes: The primes p, in which the sequence 1/2+1/3+1/5+1/7+....+1/p exceeds 0,1,2,3,....

The first few numbers, starting with 0, are 2,5,277,5195977,... (sequence A016088 in OEIS)

* The Double Mersenne numbers

* The elements of Sylvester's sequence (sequence A000058 in OEIS)

where E ≈ 1.264084735305 is Vardi's constant.

* The number of k-ary operators:

More generally, if the nth value of an integer sequences is proportional to a double exponential function of n, Ionascu and Stanica call the sequence "almost doubly-exponential" and describe conditions under which it can be defined as the floor of a doubly-exponential sequence plus a constant.[2] Additional sequences of this type include

* The prime numbers 2, 11, 1361, ... (sequence A051254 in OEIS)

where A ≈ 1.306377883863 is Mills' constant.

Applications

Algorithmic complexity

In computational complexity theory, some algorithms take double-exponential time:

* Decision procedures for Presburger arithmetic
* Computing a Gröbner basis
* Finding a complete set of associative-commutative unifiers [3]
* Satisfying CTL+ (which is, in fact, 2-EXPTIME-complete) [4]
* Quantifier elimination on real closed fields takes at least doubly-exponential time (but is not even known to be computable in ELEMENTARY)
* Calculating the complement of a regular expression

Number theory

Some number theoretical bounds are double exponential. Odd perfect numbers with n distinct prime factors are known to be at most

a result of Nielsen (2003).[5]

The largest known prime number in the electronic era has grown roughly as a double exponential function of the year since Miller and Wheeler found a 79-digit prime on EDSAC1 in 1951.[6]

Theoretical biology

In population dynamics the growth of human population is sometimes supposed to be double exponential. Gurevich and Varfolomeyev[7] experimentally fit

where N(y) is the population in year y in millions.

Physics

In the oscillator Toda model of self-pulsation, the logarithm of amplitude varies exponentially with time (for large amplitudes), thus the amplitude varies as double-exponential function of time.[8]

References

1. ^ Aho, A. V.; Sloane, N. J. A. (1973), "Some doubly exponential sequences", Fibonacci Quarterly 11: 429–437, http://www.research.att.com/~njas/doc/doubly.html .
2. ^ Ionascu, E.; Stanica, P. (2004), "Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences", Acta Mathematica Universitatis Comenianae LXXIII (1): 75–87 .
3. ^ Kapur, Deepak; Narendran, Paliath (1992), "Double-exponential complexity of computing a complete set of AC-unifiers", Proc. 7th IEEE Symp. Logic in Computer Science (LICS 1992), pp. 11–21, doi:10.1109/LICS.1992.185515, http://citeseer.ist.psu.edu/337363.html .
4. ^ Johannse, Jan; Lange, Martin (2003), "CTL+ is complete for double exponential time", in Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim et al., Proc. 30th Int. Colloq. Automata, Languages, and Programming (ICALP 2003), Lecture Notes in Computer Science, 2719, Springer-Verlag, pp. 767–775, doi:10.1007/3-540-45061-0_60, http://www.tcs.informatik.uni-muenchen.de/~mlange/papers/icalp03.pdf .
5. ^ Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: the Electronic Journal of Combinatorial Number Theory 3: A14, http://www.integers-ejcnt.org/vol3.html .
6. ^ Miller, J. C. P.; Wheeler, D. J. (1951), "Large prime numbers", Nature 168: 838, doi:10.1038/168838b0 .
7. ^ Varfolomeyev, S. D.; Gurevich, K. G. (2001), "The hyperexponential growth of the human population on a macrohistorical scale", Journal of Theoretical Biology 212 (3): 367–372, doi:10.1006/jtbi.2001.2384, PMID 11829357 .
8. ^ Kouznetsov, D.; Bisson, J.-F.; Li, J.; Ueda, K. (2007), "Self-pulsing laser as oscillator Toda: Approximation through elementary functions", Journal of Physics A 40: 1–18, doi:10.1088/1751-8113/40/9/016, http://www.iop.org/EJ/abstract/-search=15823442.1/1751-8121/40/9/016 .

Functions