Double exponential function
A double exponential function is a constant raised to the power of an exponential function. The general formula is (where a>1 and b>1), which grows much more quickly than an exponential function. For example, if a = b = 10:
Factorials grow faster than exponential functions, but much more slowly than doubly exponential functions. However, tetration and the Ackermann function grow 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
A sequence of positive integers (or real numbers) is said to have doubly exponential rate of growth if the function giving the nth term of the sequence is bounded above and below by doubly exponential functions of n. Examples 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 the OEIS)
- The Double Mersenne numbers
- The elements of Sylvester's sequence (sequence A000058 in the OEIS) where E ≈ 1.264084735305302 is Vardi's constant (sequence A076393 in the OEIS).
- The number of k-ary Boolean functions:
- The prime numbers 2, 11, 1361, ... (sequence A051254 in the OEIS) where A ≈ 1.306377883863 is Mills' constant.
Aho and Sloane observed that in several important integer sequences, each term is a constant plus the square of the previous term. They show that such sequences can be formed by rounding to the nearest integer the values of a doubly exponential function with middle exponent 2. Ionaşcu and Stănică describe some more general sufficient conditions for a sequence to be the floor of a doubly exponential sequence plus a constant.
In computational complexity theory, some algorithms take doubly exponential time:
- Each decision procedure for Presburger arithmetic provably requires at least doubly exponential time 
- Computing a Gröbner basis over a field. In the worst case, a Gröbner basis may have a number of elements which is doubly exponential in the number of variables. On the other hand, the worst-case complexity of Gröbner basis algorithms is doubly exponential in the number of variables as well as in the entry size.
- Finding a complete set of associative-commutative unifiers 
- Satisfying CTL+ (which is, in fact, 2-EXPTIME-complete) 
- Quantifier elimination on real closed fields takes doubly exponential time (see Cylindrical algebraic decomposition).
- Calculating the complement of a regular expression
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.
a result of Pikhurko.
where N(y) is the population in millions in year y.
- Aho, A. V.; Sloane, N. J. A. (1973), "Some doubly exponential sequences", Fibonacci Quarterly, 11: 429–437.
- Ionaşcu, Eugen-Julien; Stănică, Pantelimon (2004), "Effective asymptotics for some nonlinear recurrences and almost doubly-exponential sequences" (PDF), Acta Mathematica Universitatis Comenianae, LXXIII (1): 75–87.
- Fischer, M. J., and Michael O. Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic. Archived 2006-09-15 at the Wayback Machine" Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41
- Dubé, Thomas W. The structure of polynomial ideals and Gröbner bases. SIAM Journal on Computing, 1990, vol. 19, no 4, p. 750-773.
- 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, S2CID 206437926.
- Johannsen, Jan; Lange, Martin (2003), "CTL+ is complete for double exponential time", in Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim; Woeginger, Gerhard J. (eds.), Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) (PDF), 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, archived from the original (PDF) on 2007-09-30, retrieved 2006-12-22.
- Gruber, Hermann; Holzer, Markus (2008). "Finite Automata, Digraph Connectivity, and Regular Expression Size" (PDF). 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.
- 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
- Nielsen, Pace P. (2003), "An upper bound for odd perfect numbers", INTEGERS: The Electronic Journal of Combinatorial Number Theory, 3: A14.
- Pikhurko, Oleg (2001), "Lattice points in lattice polytopes", Mathematika, 48 (1–2): 15–24, arXiv:math/0008028, Bibcode:2000math......8028P, doi:10.1112/s0025579300014339
- Miller, J. C. P.; Wheeler, D. J. (1951), "Large prime numbers", Nature, 168 (4280): 838, Bibcode:1951Natur.168..838M, doi:10.1038/168838b0.
- 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.
- 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.
- Kawaguchi, Tohru; Walker, Kathleen L.; Wilkins, Charles L.; Moore, Jeffrey S. (1995). "Double Exponential Dendrimer Growth". Journal of the American Chemical Society. 117 (8): 2159–2165. doi:10.1021/ja00113a005.