Double exponential function

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. They 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. 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 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:

More generally, if the nth value of an integer sequences is proportional to a double exponential function of n, Ionaşcu and Stănică 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. Additional sequences of this type include

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

where A ≈ 1.306377883863 is Mills' constant.

Algorithmic complexity

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 h_i = 2²ⁱ (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.

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). The maximal volume of a d-lattice polytope with k ≥ 1 interior lattice points is at most

( 8 d ) d ⋅ 15 d ⋅ 2 2 d + 1

a result of 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.

Theoretical biology

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

N ( y ) = 375.6 ⋅ 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 doubly exponential function of time.