Double exponential function

A double exponential function (red curve) compared to a single exponential function (blue curve).

A double exponential function is a constant raised to the power of an exponential function. The general formula is f(x) = a^{b^x}=a^{(b^x)}, which grows much more quickly than an exponential function. For example, if a = b = 10:

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

The inverse of the double exponential function is the double logarithm ln(ln(x)).

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

F(m) = 2^{2^m}+1
The first few numbers, starting with 0, are 2,5,277,5195977,... (sequence A016088 in OEIS)
MM(p) = 2^{2^p-1}-1
s_n = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor
where E ≈ 1.264084735305302 is Vardi's constant.
2^{2^k}

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

a(n) = \left\lfloor A^{3^n}\right\rfloor
where A ≈ 1.306377883863 is Mills' constant.

Applications

Algorithmic complexity

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

In some other problems in the design and analysis of algorithms, doubly exponential sequences are used within the design of an algorithm rather than in its analysis. An example is Chan's algorithm for computing convex hulls, which performs a sequence of computations using test values hi = 22i (estimates for the eventual output size), taking time O(n log hi) for each test value in the sequence. Because of the double exponential growth of these test values, the time for each computation in the sequence grows singly-exponentially as a function of i, and the total time is dominated by the time for the final step of the sequence. Thus, the overall time for the algorithm is O(n log h) where h is the actual output size.[8]

Number theory

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

2^{4^n}

a result of Nielsen (2003).[9] The maximal volume of a d-lattice polytope with k ≥ 1 interior lattice points is at most

(8d)^d\cdot15^{d\cdot2^{2d+1}}

a result of Pikhurko.[10]

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.[11]

Theoretical biology

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

N(y)=375.6\cdot 1.00185^{1.00737^{y-1000}} \,

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

Physics

In the Toda oscillator 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.[13]

References

  1. ↑ Aho, A. V.; Sloane, N. J. A. (1973), "Some doubly exponential sequences", Fibonacci Quarterly 11: 429–437.
  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. ↑ Fischer, M. J., and Michael O. Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic." Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41
  4. ↑ Dubé, Thomas W. The structure of polynomial ideals and Gröbner bases. SIAM Journal on Computing, 1990, vol. 19, no 4, p. 750-773.
  5. ↑ 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, ISBN 0-8186-2735-2.
  6. ↑ Johannsen, Jan; Lange, Martin (2003), "CTL+ is complete for double exponential time", in Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim et al., Proceedings of the 30th International Colloquium on 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, ISBN 978-3-540-40493-4 .
  7. ↑ Gruber, Hermann; Holzer, Markus (2008). "Finite Automata, Digraph Connectivity, and Regular Expression Size". Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008) 5126. pp. 39–50. doi:10.1007/978-3-540-70583-3_4.
  8. ↑ Chan, T. M. (1996), "Optimal output-sensitive convex hull algorithms in two and three dimensions", Discrete and Computational Geometry 16 (4): 361–368, doi:10.1007/BF02712873, MR 1414961
  9. ↑ Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: the Electronic Journal of Combinatorial Number Theory 3: A14.
  10. ↑ Pikhurko, Oleg (2001), "Lattice points in lattice polytopes", Mathematika 48: pp. 15–24, arXiv:math/0008028, Bibcode:2000math......8028P, doi:10.1112/s0025579300014339
  11. ↑ Miller, J. C. P.; Wheeler, D. J. (1951), "Large prime numbers", Nature 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0.
  12. ↑ 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.
  13. ↑ 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 (9): 1–18, Bibcode:2007JPhA...40.2107K, doi:10.1088/1751-8113/40/9/016.