Double exponential function

Double exponential sequences

A sequence of positive integers (or real numbers) is said to have double exponential rate of growth if the function giving the nth term of the sequence is bounded above and below by double exponential functions of n. Examples include

• The Fermat numbers F(m) = 2^{2^m}+1
• 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, ...
• The Double Mersenne numbers MM(p) = 2^{2^p-1}-1
• The elements of Sylvester's sequence s_n = \left\lfloor E^{2^{n+1}}+\frac12 \right\rfloor where E ≈ 1.264084735305302 is Vardi's constant .
• The number of k-ary Boolean functions: 2^{2^k}
• The prime numbers 2, 11, 1361, ... a(n) = \left\lfloor A^{3^n}\right\rfloor 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 double 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 double exponential sequence plus a constant.{{citation

Applications

Algorithmic complexity

In computational complexity theory, 2-EXPTIME is the class of decision problems solvable in double exponential time. It is equivalent to AEXPSPACE, the set of decision problems solvable by an alternating Turing machine in exponential space, and is a superset of EXPSPACE. An example of a problem in 2-EXPTIME that is not in EXPTIME is the problem of proving or disproving statements in Presburger arithmetic.

In some other problems in the design and analysis of algorithms, double 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 h**i = 22i (estimates for the eventual output size), taking time O(n log h**i) 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.{{citation

In a different direction, Witteveen & Jeffery showed that any QMA protocol can be amplified (see BPP) to have doubly-exponential error (with mild constraints on choice of gate sets).

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).{{citation

The maximal volume of a polytope in a d-dimensional integer lattice with k ≥ 1 interior lattice points is at most :k\cdot(8d)^d\cdot15^{d\cdot2^{2d+1}}, a result of Pikhurko (2001).{{citation|last=Pikhurko

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.{{citation

Theoretical biology

In population dynamics the growth of human population is sometimes supposed to be double exponential. Varfolomeyev and Gurevich{{citation

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

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

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.{{citation

Dendritic macromolecules have been observed to grow in a doubly-exponential fashion.

References

References

1. (1973). "Some doubly exponential sequences". [[Fibonacci Quarterly]].
2. [[Christos Papadimitriou]], Computational Complexity (1994), {{isbn. 978-0-201-53082-7. Section 20.1, corollary 3, page 495.
3. [[Michael J. Fischer. Fischer, M. J.]], and [[Michael O. Rabin]], 1974, "[http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps "Super-Exponential Complexity of Presburger Arithmetic.] {{Webarchive. link. (2006-09-15 " ''Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7'': 27–41)
4. (2025). "${\sf QMA}={\sf QMA}_1$ with an infinite counter".
5. (1995). "Double Exponential Dendrimer Growth". [[Journal of the American Chemical Society]].